【劍指offer+撲克牌順子+數學模組化+模拟】

【題目連結】：​​http://ac.jobdu.com/problem.php?pid=1355​​

【題目描述】：

題目1355：撲克牌順子

時間限制：2 秒

記憶體限制：32 兆

特殊判題：否

送出：1806

解決：530

題目描述：

LL今天心情特别好,因為他去買了一副撲克牌,發現裡面居然有2個大王,2個小王(一副牌原本是54張^_^)...他随機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿！！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大\小 王可以看成任何數字,并且A看作1,J為11,Q為12,K為13。上面的5張牌就可以變成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL決定去買體育彩票啦。

現在,要求你使用這幅牌模拟上面的過程,然後告訴我們LL的運氣如何。為了友善起見,你可以認為大小王是0。

輸入：

輸入有多組資料。

每組資料包含兩行,第一行輸入一個正數n(0<=n<=14),表示從撲克牌中抽出的撲克牌數。接下來的一行輸入n個數,表示從這幅撲克牌中抽出的牌。如果n=0,則結束輸入。

輸出：

對應每組資料,如果抽出的牌是順子,則輸出“So Lucky!”。否則,輸出“Oh My God!”。

樣例輸入：

5

3 5 1 0 4

5

3 5 4 7 6

5

3 5 7 4 8

樣例輸出：

So Lucky!

So Lucky!

Oh My God!

【思路】：

把撲克牌的背景抽象成計算機語言，即把五張牌看成由5個數字組成的數組。大小王看做事特殊的數字，不妨把它們定義為0，這樣就能和其他牌區分開來。

【代碼】：

/***********************
劍指offer 撲克牌順序【模拟】
Author：herongwei
Time:2017/5/12 19:00
language：C++
***********************/
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#define rep(i,k,n) for(int i=k;i<=n;++i)
#define rep2(i,k,n) for(int i=k;i>=n;--i)
using namespace std;
const int maxn= 1e2+233;
const int N= 1e6;
const int MOD = 1e9+7;
typedef long long LL;
int t,n,m,k,ret,ans,tot=0;
int arr[15];

inline int read(){
    int  c=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
    return c*f;
}

void quick_sort(int* arr, int l, int r){
    if(l<r){
        ///Swap(s[l], s[(l + r) / 2]); 将中間的這個數和第一個數交換 參見注1
        int i=l, j=r, tp=arr[l];
        while(i<j)
        {
            while(i<j&&arr[j]>=tp)j--; /// 從右向左找第一個小于tp的數  j--;
            if(i<j)arr[i++]=arr[j];
            while(i<j&&arr[i]<=tp)i++; /// 從左向右找第一個大于等于tp的數  i++;
            if(i<j)arr[j--]=arr[i];
        }
        arr[i] = tp;
        quick_sort(arr,l,i-1); /// 遞歸調用
        quick_sort(arr,i+1,r);
    }
}

/// 0 1 3 4 5
bool is_continuous(int* arr,int n){
    if(arr==NULL || n<1) return false;
    quick_sort(arr,1,n);///先排序使得序列有序
    /// rep(i,1,n) cout<<arr[i]<<" ";;
    int num_zero = 0;   ///統計0的個數
    int num_gap  = 0;   ///統計缺位的個數
    for(int i=1; i<=n && arr[i]==0;++i) ++num_zero;
    int small=num_zero+1;
    int big  = small+1;
    while(big<n){      ///  循環o(n)查找缺位個數
        if(arr[big]==arr[small]) return false;
        num_gap += arr[big]-arr[small]-1;
        small=big;
        ++big;
    }
   // cout<<num_gap<<" "<<num_zero<<endl;
    return num_gap<=num_zero?true:false;
}
int main(){
  //  freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
    while(~scanf("%d",&n)&&n){
        memset(arr,0,sizeof(arr));
        rep(i,1,n) arr[i]=read();
        if(is_continuous(arr,n))puts("So Lucky!");
        else puts("Oh My God!");
    }
    return 0;
}