bzoj 1028: [JSOI2007]麻将 （贪心）

题目描述

传送门

题解

枚举听牌和对子，然后剩下的牌贪心的去判定。 假设当前判断到i，那么cnt[i]先模3，然后让cnt[i+1]-=cnt[i],cnt[i+2]-=cnt[i]，最后如果没有牌的数量<0，则成立。 注意对于还没有判断的牌的个数不能先模3，要不如果前面的牌需要利用这个牌形成对子的时候就不能构成了。

代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define N 10003 using namespace std; int a[N],cnt[N],n,m,ans[N]; int main() { scanf("%d%d",&n,&m); m=3*m+1; for (int i=1;i<=m;i++) { int x; scanf("%d",&x); cnt[x]++; } bool mark=false; for (int i=1;i<=n;i++) for (int k=1;k<=n;k++) if (cnt[k]>=2||cnt[k]==1&&i==k){ for (int j=1;j<=n;j++) { a[j]=(j==i?1:0); if (j==k) a[j]+=(cnt[j]-2); else a[j]+=cnt[j]; } a[n+1]=a[n+2]=0; bool pd=true; for (int j=1;j<=n;j++){ if (a[j]<0) { pd=false; break; } a[j]%=3; a[j+1]-=a[j]; a[j+2]-=a[j]; } if (a[n+1]<0||a[n+2]<0) pd=false; if (pd) { mark=true; ans[++ans[0]]=i; break; } } for (int i=1;i<=ans[0]-1;i++) printf("%d ",ans[i]); if (ans[0]) printf("%d\n",ans[ans[0]]); if (!mark) printf("NO\n"); }