BZOJ 1028 JSOI 2007 麻将 贪心
题目大意
给出一种简化的麻将游戏规则,给出一副牌,问是否听牌,如果听,听那些张。
思路
一开始图样,写搜索,果断T了。
其实就是一个显然的贪心。枚举听哪张牌,加进来,然后枚举最后剩下的雀头,对剩下的牌尽量组成m个顺子或者对子就行了。这时候我们从左往右扫,能够组成对子的就形成对子,不能的就和后面组成顺子。遇到小于0的就退出就好了。
CODE
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 10010
using namespace std;
int cnt, m;
int src[MAX];
int num[410];
int ans[MAX], total;
inline bool Judge()
{
static int arr[MAX];
for(int i = 1; i <= cnt + 2; ++i)
arr[i] = num[i];
for(int i = 1; i <= cnt + 2; ++i) {
if(arr[i] < 0) return false;
arr[i] %= 3;
arr[i + 1] -= arr[i];
arr[i + 2] -= arr[i];
}
return true;
}
int main()
{
cin >> cnt >> m;
for(int i = 1; i <= 3 * m + 1; ++i)
scanf("%d", &src[i]);
for(int i = 1; i <= cnt; ++i) {
src[3 * m + 2] = i;
memset(num, 0, sizeof(num));
for(int j = 1; j <= 3 * m + 2; ++j)
++num[src[j]];
for(int j = 1; j <= cnt; ++j)
if(num[j] >= 2) {
num[j] -= 2;
if(Judge()) {
ans[++total] = i;
break;
}
num[j] += 2;
}
}
if(!total)
puts("NO");
for(int i = 1; i <= total; ++i)
printf("%d%c", ans[i], " \n"[i == total]);
return 0;
}
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。