当前位置：首页 > news >正文

B-名牌赌王（本人遇到的题，做个笔记）

news 2025/8/23 12:48:56

题解：

#include <iostream>
#include <queue>			//需要用小根堆的优先队列
#include <unordered_map>		//用无序映射
using namespace std;
bool pai()				
{int n, m;cin >> n >> m;		priority_queue<int, vector<int>, greater<int>>q;		//用来往里面存牌unordered_map<int, int>arr;		//记录每张牌的个数while (n--){int num;cin >> num;		//输入当前的牌arr[num]++;		//将当前牌的数量加1q.push(num);		//往优先队列里插入该牌}while (!q.empty())		//根据队列里面个数去循环（只要队列不为空就循环）{int number = q.top();		//将队列的堆顶元素（最小值）记录下来q.pop();			//必须得先弹出再去判断这个牌的数量if (arr[number] == 0)	continue;		//如果当前牌的个数为0，则开始下一次循环for (int i = 0; i < m; i++)			//根据每组顺子的长度去循环{int cnt = arr[number+i]--;		//用cnt记录当前牌的个数，记录后，就让当前牌个数-1，因为当前牌构成了顺子，且索引是number+i，因为只有连着的才能构成顺子if (cnt == 0)	return false;			//如果要构成顺子的该牌数量为0，则表示无法构成顺子，返回false}}return true;		//若能顺利构成若干组m长度的顺子，则返回true}
int main()
{int t;cin >> t;while (t--){if (pai())	cout << "YES" << endl;else cout << "NO" << endl;}}

以前写的代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{int t;cin >> t;		//有几副牌vector<int>arr;		//定义的数组来放牌while (t--)		//根据t是多少来循环几次{int n, m;cin >> n >> m;		//输入1副牌的数量以及顺子长度arr.resize(n);for (int i = 0; i < n; i++)	cin >> arr[i];sort(arr.begin(), arr.end(), less<int>());		//将牌从小到大排序int min = 0;	//顺子最开始的那个牌int flag = 0;		//去判断有没有找到顺子的头int count = 0;		//去计算该顺子的目前长度int zushu = 0;		//有几组顺子bool zuizhonflag = 1;		//去判断最终能否符合题中条件，即若干组m长度的顺子if (n % m == 0)		{zushu = n / m;		//来记录顺子有几组}else    //如果不能组成若干组长度为m的顺子则直接终止，看下一副牌{cout << "No" << endl;continue;}while (zushu--)		//有几组顺子就循环几次{zuizhonflag = 1;		//先假设符合题意，能组成若干组长度为m的顺子count = 0;		//将目前顺子长度定义为0flag = 0;		//0表示还没有找到顺子的头for (int i = 0; i < n; i++)		//遍历该副牌{if (arr[i] != 0 && flag == 0)		//若flag=0,且找到第一个不是0的牌，则该牌为顺子的头，用min记录{min = arr[i];arr[i] = 0;		//将该牌删去，记录为0flag = 1;		//1表示找到顺子的头了count++;		//顺子长度加1}if (flag == 1 && arr[i] == min + 1)		//若存在顺子的头，且该牌是顺子中的下一个牌（比如，顺子头是2，则要找3）{min = arr[i];		//则将min记录为arr[i](找到3后，把min记录为3，方便去找4)arr[i] = 0;		//将该牌删去count++;		//顺子长度加1}if (count == m)	break;		//若顺子长度到了所规定的m长，则跳出for循环，开始找下一组顺子}if (count != m)			//若遍历完for循环，发现顺子长度不够，则该副牌不符合题意{zuizhonflag = 0;cout << "No" << endl;		//输出No,跳出while循环，开始下一副牌break;}}if (zuizhonflag == 1)			//若该副牌符合题意，则输出YES，并清空vector容器{cout << "Yes" << endl;}arr.clear();		//清空容器}return 0;
}