Duizi and Shunzi
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 245 Accepted Submission(s): 115
Problem Description
Nike likes playing cards and makes a problem of it.
Now give you n integers,
ai(1≤i≤n)
We define two identical numbers (eg:
2,2
) a Duizi,
and three consecutive positive integers (eg:
2,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)
.
Each number can be used only once.
Input
The input contains several test cases.
For each test case, the first line contains one integer n(
1≤n≤106
).
Then the next line contains n space-separated integers
ai
(
1≤ai≤n
)
Output
For 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 5
Sample 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）
Source
2017ACM/ICPC广西邀请赛-重现赛（感谢广西大学）
Recommend
liuyiding | We have carefully selected several similar problems for you:
6193
6192
6191
6190
6189
Statistic |
Submit |
Discuss |
Note
输入一个n，接下来有n个数，让你求出能组成最多的对子或者顺子的和。
对子: (2,2)，顺子: (1,2,3)。
贪心思路，优先考虑对子，其次是顺子，详见代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <list>
#include <bitset>
#include <stack>
#include <stdlib.h>
#define lowbit(x) (x&-x)
#define e exp(1.0)
#define eps 1e-8
//ios::sync_with_stdio(false);
// auto start = clock();
// cout << (clock() - start) / (double)CLOCKS_PER_SEC<<endl;
typedef long long ll;
typedef long long LL;
using namespace std;
typedef unsigned long long ull;
const int maxn=1e6+10;
int a[maxn];
int main()
{
ios::sync_with_stdio(false);
int n;
while(cin>>n)
{
int x;
memset(a,0,sizeof(a));
for(int i=0;i<n;i++)
cin>>x,a[x]++;
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=(a[i]/2);
a[i]%=2;
if(i+1<n)
{
if(a[i]==1 && a[i+1]%2 && a[i+2])
{
ans++;
a[i]--;
a[i+1]--;
a[i+2]--;
}
}
}
cout<<ans<<endl;
}
return 0;
}
