hdu6188 Duizi and Shunzi(贪心)

思路来源

https://blog.csdn.net/qq_37497322/article/details/77851437

题意

有若干张牌，三个连续数字组成一个顺子，两个相同数字组成一个对，

求最大的顺字数+对数。

题解

从最大到最小遍历，能用两个相同的构成对就构成对，

如果a[v]最后还剩一张，说明这张要被弃掉了；

再去看a[v-1]是不是奇数张，是的话说明也有一张要被弃掉；

如果出现这种情况，就用一张a[v-2]来救这两张废弃牌。

这样，我们就用一张非废弃牌凑齐了一个贡献，

而常规操作下，一个顺需要三张非废弃牌，一个对需要两张废弃牌，显然是更优的。

心得

贪心真的好迷啊……

自己之前想了一个伪算法，先凑顺，再凑对，

最后把个数大于等于2的顺，如1 2 3 1 2 3这种还原回三个对，

然而WA了。

不过现在想想，1 1 2 2 3直接就能ban掉该伪算法。

还是太菜了……

代码

#include <iostream>
#include <algorithm> 
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <bitset> 
const int INF=0x3f3f3f3f;
const int maxn=1e6+5;
const int mod=1e9+7;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<int,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std;
int n,a[maxn],top,ans;
int main()
{
	while(~scanf("%d",&n))
	{
		mem(a,0);top=0;ans=0;
		rep(i,0,n-1)
		{
			int v;
			sci(v);
			a[v]++;
			top=max(top,v);
		}
		per(j,top,1)
		{
			ans+=a[j]/2;
			a[j]%=2;
			if(j>=3&&(a[j]%2)&&(a[j-1]%2)&&a[j-2])ans++,a[j]=0,a[j-1]--,a[j-2]--;
		}
		printf("%d\n",ans);
	}
	return 0;
}