HDU6188 (Duizi and Shunzi)[贪心]

发表于 | 更新于 | | 阅读次数：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6188

一个对子只消耗两张牌，相对于顺子更加「实惠」。考虑这样一个贪心策略：先把每种牌能换成对子就换成对子，此时每种牌一定只有一张或零张。对于一种牌i，如果i有一张，且i+1也有一张，那么只要i+2初始时有牌就把i，i+1，i+2换成一个顺子，这样做最多是一个对子换顺子，而且可能会在i+2的位置多留出一张牌。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000009;

int a[maxn];
int b[maxn];
int cnt[maxn];
int n;

int main() {
	while(~scanf("%d",&n)) {
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(cnt,0,sizeof(cnt));
		int c=0;
		for(int i=1;i<=n;i++) scanf("%d",a+i);
		sort(a+1,a+n+1);
		for(int i=1;i<=n;i++) b[a[i]]++;
		for(int i=1;i<=n;i++) cnt[i]=b[i]/2,b[i]%=2;
		for(int i=1;i<=n-2;i++) 
			if(b[i] && b[i+1] && (b[i+2]||cnt[i+2])) {
				c++;
				b[i]--;
				b[i+1]--;
				if(b[i+2]) b[i+2]--;
				else {
					cnt[i+2]--;
					b[i+2]++;
				}
			}
		int ans=c;
		for(int i=1;i<=n;i++) ans+=cnt[i];
		printf("%d\n",ans);
	}
}