老师的题解

心态好

2025-07-31 20:17:55

发布于：河北

6阅读

0回复

0点赞

瞪眼法易得：本题的主要考核内容是贪心
老师抓住了每张卡牌只能攻击一次的特点，将按r非降序排序后的卡牌放入队列并判断是否有卡牌出局，最终所有没有出局的卡牌都被存储与队列中，最终输出size即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;
int n;
queue<int> q;
int r[N];
int main()
{
	q.push(0);//保证有队首
	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> r[i];
		sort(r+1,r+n+1);//按r非降序排序
	for(int i = 1;i <= n;i++)
	{
		int u = q.front();
		if(u < r[i])//判断是否有卡牌出局
			q.pop();
		q.push(r[i]);
	}
	cout << q.size();
	return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 1

心态好

555我的代码TLE了，有没有大佬能帮忙改改
（思路主要是让尽可能小的卡牌先行动，不浪费大牌点数）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;
int n;
int r[N];
bool vis[N];
int main()
{
	cin >> n;
    int ans = n;
	for(int i = 1;i <= n;i++)
		cin >> r[i];
	sort(r+1,r+n+1);
    int pre = -1;//通过记录上一张比第i张大的牌剪枝 
    for(int i = 1;i <= n;i++)//遍历r数组寻找可以被出局的牌 
    {
    	for(int j = (pre != -1?pre+1:i+1);j <= n;j++)
    	{
	        if(r[i] < r[j] && !vis[j])//可以攻击 
	        {
                ans--;
                pre = j;
                vis[i] = 
                vis[j] = 1; 
	        	break;
	        }
        }
    }
    cout << ans;
	return 0;
}

3天前来自河北