欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

tokitsukaze and Soldier

程序员文章站 2022-03-21 17:25:49
...
题目链接

题意:

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

分析:
tokitsukaze and Soldier
嗯,看了题解才知道怎么贪心
将士兵按 s 由大到小的顺序排序,即从大到小枚举每个 s ,那么当前士兵的战力 v 加入团中(放入小顶堆),如果团的人数超过当前的限制人数 s ,将小顶堆中最小的减去,直到人数为 s, 维护最大值。

#include <iostream>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <cstdio>
#include <algorithm>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int mod=1e9+7;
const int maxn=1e5+10;
int n;

struct Node{
	ll v,s;
}a[maxn]; 

bool cmp(Node x, Node y){
	return x.s>y.s; 
}

priority_queue <int,vector<int>,greater<int> > res;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for (int i=0; i<n; i++) {
		cin>>a[i].v>>a[i].s;
	}
	sort(a,a+n,cmp);
	ll ans=0;
	ll sum=0;
	for (int i=0; i<n; i++){
		sum+=a[i].v;
		res.push(a[i].v);
		while (res.size()>a[i].s){
			sum-=res.top();
			res.pop();
		}
		ans=max(ans,sum);
	}
	
	cout<<ans<<endl;
	
	return 0;
}
相关标签: 每日一题