HDU6188 duizi and shunzi
Nike likes playing cards and makes a problem of it.
Now give you n integers, ai(1≤i≤n)ai(1≤i≤n)
We define two identical numbers (eg: 2,22,2) a Duizi,
and three consecutive positive integers (eg: 2,3,42,3,4) a Shunzi.
Now you want to use these integers to form Shunzi and Duizi as many as possible.
Let s be the total number of the Shunzi and the Duizi you formed.
Try to calculate max(s)max(s).
Each number can be used only once.
InputThe input contains several test cases. Now give you n integers, ai(1≤i≤n)ai(1≤i≤n)
We define two identical numbers (eg: 2,22,2) a Duizi,
and three consecutive positive integers (eg: 2,3,42,3,4) a Shunzi.
Now you want to use these integers to form Shunzi and Duizi as many as possible.
Let s be the total number of the Shunzi and the Duizi you formed.
Try to calculate max(s)max(s).
Each number can be used only once.
For each test case, the first line contains one integer n( 1≤n≤1061≤n≤106).
Then the next line contains n space-separated integers aiai ( 1≤ai≤n1≤ai≤n)
OutputFor each test case, output the answer in a line.
Sample Input
7 1 2 3 4 5 6 7 9 1 1 1 2 2 2 3 3 3 6 2 2 3 3 3 3 6 1 2 3 3 4 5Sample Output
2
4
3
2
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）
其实就是个贪心，在可组成顺子的牌数少于两张的时候优先打对子，但是如果顺子的牌的数量超过两张，那么第三张无论如何都要组成顺子。
错了三次，一次没有清数组，一次忘记第一张牌就可以打对子的情况，最后一次是当打出顺子的时候没有对记录数组减一。
#include<iostream>
#include<algorithm>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
using namespace std;
int p[1000005];
int t[1000005];
int main()
{
int n;
while (~scanf("%d",&n))
{
memset(t, 0, sizeof(t));
for (int i = 0; i < n; i++)
{
scanf("%d", &p[i]);
t[p[i]]++;
}
sort(p, p + n);
int last = 0;
int temp = 0;
int ans = 0;
for (int i = 0; i < n; i++)
{
if (temp == 0)
{
last = p[i];
temp++;
if (t[p[i]]>=2)
{
ans++;
t[p[i]] -= 2;
temp = 0;
i++;
}
}
else
{
if (temp == 2 && last == p[i] - 1)
{
ans++;
temp = 0;
t[p[i]]--;
}
else if (t[p[i]] >= 2)
{
t[p[i]] -= 2;
ans++;
i++;
}
else if(last != p[i] - 1)
{
temp = 0;
last = p[i];
temp++;
}
else if (last == p[i] - 1)
{
temp++;
last = p[i];
t[p[i]]--;
}
}
}
cout << ans << endl;
}
return 0;
}
