刷题记录:牛客NC50439tokitsukaze and Soldier

传送门:牛客

题目描述:

在一个游戏中，tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。
第i个士兵的战力为v[i]，团的战力是团内所有士兵的战力之和。
但是这些士兵有特殊的要求：如果选了第i个士兵，这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵，就没有这个限制。)
tokitsukaze想知道，团的战力最大为多少。
输入:
2
1 2
2 2
输出:
3

首先这道题算是一个比较简单的单调队列的题目,稍微思考一下就会出现一种贪心的想法

主要思路:

1. 首先我们将士兵按照希望人数按照从大到小进行一个排序,为什么这样排序呢,因为我们假设一个希望人数为K的人能够进入我们的队列之中,那么此时我们的总人数肯定是<=K的,那么此时如果我们有一个大于K的人,那么此时这个人肯定是可以进入我们的队伍之中的.
2. 排完序之后,我们准备一个优先队列来维护我们的进入的人,每次加入一个人,都将其的希望人数与我们的队列大小进行比较(包括刚加入的),如果不行,则去除原先队列中的战力最小的(此时因为我们使用优先队列维护了,所以这个就是top()),为什么我们可以这么做呢,因为此时因为这个人,我们有两种方案,一是加入这个人,二是不加入这个人,加入这个人我们肯定要满足要求,如果选择不加入这个人我们还是需要去除不满足这个人的人,因为之后的人的条件只会越来越苛刻

本题我直接采用STL来解决问题

具体代码:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n;
struct Peo{
	int v,s;
}peo[maxn];
bool cmp(Peo a,Peo b) {
	return a.s>b.s;
}
struct ccmp{
	bool operator() (const int a,const int b) const{
		return a>b;
	}
};
priority_queue<int,vector<int>,ccmp>q;
int main() {
	n=read();
	for(int i=1;i<=n;i++) {
		peo[i].v=read();
		peo[i].s=read();
	}
	sort(peo+1,peo+n+1,cmp);
	ll maxx=-inf;ll ans=0;
	for(int i=1;i<=n;i++) {
		q.push(peo[i].v);
		ans+=peo[i].v;
		while(q.size()>peo[i].s){
			ans-=q.top();
			q.pop();
		}
		maxx=max(maxx,ans);
	}
	cout<<maxx<<endl;
	return 0;
}