广西邀请赛的一道题，按出题人来说是一道签到题，重现赛的时候在这道题上卡了很久，一上来以为是dp，怎么都推不出公式。后来看看题解，发现和我dp时思路是一样的，改成贪心就对了。 贪心思路： 当前数能作为某个顺子的最大值，则取顺子； 否则能取对子，则取对子。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100005; int n,a[maxn]; int cal(int mx) { int sum = 0; for(int i=1; i<=mx; i++) { if(a[i-2]>0 && a[i-1]>0 && a[i]>0 && i>=3) { sum++; a[i]--; a[i-1]--; a[i-2]--; } sum += a[i]/2; a[i] %= 2; } return sum; } int main() { while(scanf("%d",&n) !=EOF) { memset(a, 0, sizeof(a)); int mx = 0; for(int i=0; i<n; i++) { int t; scanf("%d",&t); if(mx < t) mx = t; a[t]++; } printf("%d\n",cal(mx)); } return 0; }