1571. 【基础赛】游戏(game)
(Input: game.in, Output: game.out)
题目描述
Introl 在玩一种特殊的游戏——凑顺子。
他现在有 n 张牌,每张牌的点数为 ai,他希望凑出尽可能多的顺子。
在该游戏中,顺子的定义为:点数大小连续的 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 个数,表示每张牌的点数 ai。
输出
输出到文件 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≤ai≤100。
#include<bits/stdc++.h>
using namespace std;
int a[205],n,ans;//表示:牌,牌总数,计数器
int main()
{
freopen("game.in","r",stdin);//文件输入
freopen("game.out","w",stdout);//文件输出
scanf("%d",&n);//输入n
int max1=0,min1=200;//最大,小值变量
for(int i=1;i<=n;i++)//输入每个数
{
int x;//输入变量
scanf("%d",&x);//输入每张牌
a[x]++;//对应的牌数++
min1=min(min1,x);//找最小值
max1=max(max1,x);//找最大值
}
for(int i=min1;i<=max1;i++)//凑牌开始
while(a[i]>0)//还有这张牌
{
int j=i+1;//从下一张开始计算
while(a[j]>0)//每一个下一张!=0
{
a[j]--;//这张牌--
j++;//指向下一个位置
}
if(j!=i+1)ans++;//判断是否满足顺子条件
a[i]--;//减一张
}
printf("%d",ans);//输出
}