当前位置: 代码迷 >> 综合 >> 模拟+贪心 [JSOI2007]麻将
  详细解决方案

模拟+贪心 [JSOI2007]麻将

热度:42   发布时间:2023-12-08 14:38:33.0

模拟没啥好说的,你要打麻将也会遍历一遍你要什么牌,所以要把所有扫一遍。
首先枚举对子,因为对子只有一个,特殊枚举出来。
然后贪心:先枚举刻子,再枚举顺子。但是是在挨个枚举1~n的基础上,优先找刻子。而且要在这一位能用光的基础上,才去搞下一位。这样有效避免了1 2 2 3 3 3 3 3 4 4 5的情况(如果单纯先枚举刻子,会去掉 3 3 3),但他应该是在3个顺子里。

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define N 405
using namespace std;
int n,m,a[N],b[N];
bool check()
{memcpy(b,a,sizeof(a));for(int i=1;i<=n;i++)while(b[i]){if(b[i]>=3){b[i]%=3;continue;}if(i<=n-2&&b[i]&&b[i+2]&&b[i+1]){int s=min(b[i],min(b[i+2],b[i+1]));b[i]-=s,b[i+2]-=s,b[i+1]-=s;continue;}return 0;}return 1;
}
int main()
{scanf("%d%d",&n,&m);int cnt=0,x;for(int i=1;i<=3*m+1;i++)scanf("%d",&x),a[x]++;for(int i=1;i<=n;i++){a[i]++;for(int j=1;j<=n;j++)if(a[j]>=2){a[j]-=2;if(check()){
   printf("%d ",i),cnt++;a[j]+=2;break;}a[j]+=2;}a[i]--;}if(cnt==0)printf("NO\n");else printf("\n");
}