首页 > > 程序设计 > C/C++ >

Duizi and Shunzi HDU - 6188 (贪心）2017 广西A…

2018-09-10 00:58:17来源：博客园阅读 ()

Duizi and Shunzi

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2883 Accepted Submission(s): 1110

Problem Description

Nike likes playing cards and makes a problem of it.

Now give you n integers,

Input

The input contains several test cases.

For each test case, the first line contains one integer n(

Output

For each test case, output the answer in a line.

Sample Input

1 2 3 4 5 6 7

1 1 1 2 2 2 3 3 3

2 2 3 3 3 3

1 2 3 3 4 5

Sample Output

Hint

Case 1（1，2，3）（4，5，6）

Case 2（1，2，3）（1，1）（2，2）（3，3）

Case 3（2，2）（3，3）（3，3）

Case 4（1，2，3）（3，4，5）

Source

2017ACM/ICPC广西邀请赛-重现赛（感谢广西大学）

题意：输入一个n，然后输入n张牌，每张牌都不大于n，问可以组成最多的对子数和顺子数，对子是两个相同的牌，顺子是连续的三张牌

思路：从1到n遍历，如果第 i 张牌能打完对子还有多一张，那么看 i+1 张打完对子是不是可以多，如果多的话只要 i+2 有这张牌就可以打出一个顺子，在计算第 i 张牌的时候记得把对子的数量加进去，在可以组成顺子的时候记得把第 i+1 和 i +2 凑顺子的那一张牌减掉。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-10
#define PI acos(-1.0)
#define _e exp(1.0)
#define ll long long
const int maxn=1e6+5;
int a[maxn];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(a));
        int t;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&t);
            a[t]++;
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=a[i]/2;
            if(i<=n-2 && a[i]%2 && a[i+1]%2 && a[i+2])
            {
                ans++;
                a[i]--;
                a[i+1]--;
                a[i+2]--;
            }
        }
        printf("%d\n",ans);
    }
}