[每日一题]3.24 tokitsukaze and Soldier
题目网址:https://ac.nowcoder.com/acm/problem/50439
涉及知识点:
- 优先队列/贪心
做法:
- 每个士兵都有战力Vi和一个限制Si,我们先按照每个士兵的Si从大到小进行排序
- 然后我们根据排好序的士兵遍历
- 因为士兵的Si从大到小,所以遍历的过程中,当前遍历的士兵对应的si一定是最小
- 所以我们可以维护一个大小由Si较小的优先队列
- 如果队列大小小于当前遍历士兵的Si,就扔到优先队列里,一旦士兵的人数超过限制,出队,直到队列大小等于当前士兵的Si减一
std:
#include <bits/stdc++.h> using namespace std; #define ll long long const int maxn = 1e5 + 5; struct node{ ll v; int s; }; node a[maxn]; bool cmp(node p1,node p2){ return p1.s > p2.s; } priority_queue< ll ,vector<ll>,greater<ll> > q;//小根堆 int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lld %d",&a[i].v,&a[i].s); } sort(a+1,a+1+n,cmp); ll ans = 0 , cnt = 0; for(int i=1;i<=n;i++){ while(q.size() >= a[i].s){ cnt -= q.top(); q.pop(); } q.push(a[i].v); cnt += a[i].v; ans = max(ans , cnt); } printf("%lld\n",ans); return 0; }
acm菜鸡日常 文章被收录于专栏
一般写一些打过的比赛题解以及不会的算法