tokitsukaze and Soldier
程序员文章站
2022-03-21 17:25:49
...
题目链接
题意:
在一个游戏中,tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。
第i个士兵的战力为v[i],团的战力是团内所有士兵的战力之和。
但是这些士兵有特殊的要求:如果选了第i个士兵,这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵,就没有这个限制。)
tokitsukaze想知道,团的战力最大为多少。
分析:嗯,看了题解才知道怎么贪心
将士兵按 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;
}
下一篇: make和new关键字的区别及实现原
推荐阅读
-
A. Soldier and Bananas
-
[HDU多校2020]第三场 1004 Tokitsukaze and Multiple (贪心/dp)
-
Tokitsukaze and Rescue----------------------思维(spfa+dfs)
-
tokitsukaze and Inverse Number(树状数组+逆序对定理)
-
tokitsukaze and Soldier(3月25日题目 贪心、优先队列、堆)
-
Soldier and Traveling codeforces546E (最大流好题)
-
HDU 6793 :Tokitsukaze and Colorful Tree(思维 + 离线 + 树状数组)
-
tokitsukaze and Inverse Number ( 逆序数定理 + 思维 )
-
tokitsukaze and Soldier 贪心
-
【牛客每日一题】tokitsukaze and Soldier 题目精讲 贪心、优先队列、堆