1571.游戏（game）

Question

题目描述
Introl在玩一种特殊的游戏—凑顺子。

他现在有 n 张牌，每张牌的点数为 a
i
​
，他希望凑出尽可能多的顺子。

在该游戏中，顺子的定义为：点数大小连续的 m 张牌（m>1)，不能中断，不能重复。

例如 [1,2,3,4,5,6,7,] 是一个顺子，而 [1,2,4,5,6,7,8,9] 和 [1,2,2,3,4,5,6,7,8,9] 不是一个顺子。

需要注意的是，顺子不可以拆分，例如 [1,2,3,4,5,6,7,8,9] 不可以拆分成 [1,2,3,4]、[5,6,7,8,9] 两个顺子。

换句话说，先凑最长的顺子，剩下的牌再凑最长的顺子，以此类推，直到不能凑顺子为止，顺子长度最短为 2。

输入
从文件 game.in 中读入数据。

第一行输入一个正整数 N ，表示牌的个数。

第二行输入 N 个数，表示每张牌的点数 a
i
​
。

输出
输出到文件 game.out 中。

输出顺子的个数。

样例数据
输入 #1 复制
13
2 1 2 3 5 4 4 3 5 8 7 6 9
输出 #1 复制
2

数据范围限制
对于30% 的数据，1≤N≤10。

对于100% 的数据，1≤N≤1000,1≤a
i
​
≤100。

Answer 1

```c++
#include<bits/stdc++.h>
using namespace std;
int a[1000001],s[1000001];
int main()
{
    int n;
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[a[i]]++;
    }
    int ans=0;
    bool q=1;
    while(1)
    {
        for(int i=1;i<=100;i++)
        {
            if(s[i]!=0)
            {
                for(int j=i+1;;j++)
                {
                    if(s[j]==0)
                    {
                        if(j!=i+1)
                        {
                            ans++;
                            s[i]--;
                        }
                        break;
                    }
                    else
                    s[j]--;
                }
            }
        }
        q=0;
        for(int i=1;i<=100;i++)
        {
            if(s[i]!=0&&s[i+1]!=0)
            q=1;
        }
        if(!q)
        break;
    }
    cout<<ans;
}

```