牛客练习赛50 C tokitsukaze and Soldier

链接：

来源：牛客网

题目描述

在一个游戏中，tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。

第i个士兵的战力为v[i]，团的战力是团内所有士兵的战力之和。

但是这些士兵有特殊的要求：如果选了第i个士兵，这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵，就没有这个限制。)

tokitsukaze想知道，团的战力最大为多少。

输入描述:

第一行包含一个正整数n(1≤n≤10^5)。接下来n行，每行包括2个正整数v,s(1≤v≤10^9,1≤s≤n)。

输出描述:

输出一个正整数，表示团的最大战力。

示例1

输入

复制

21 22 2

输出

复制

示例2

输入

复制

31 32 3100 1

输出

复制

题解：

贪心，先按s从大到小排序，如果要选第i个士兵，如果已选的人数已经超过了s[i]，就把已选的人里面战力最小的去掉（用优先队列实现），遍历一遍找maxn（代码易懂

#include 
    
     #include 
     
      #include 
      
       using namespace std;struct node{    int v, s;}a[100010];priority_queue

, greater

>q;bool cmp(node x, node y) { return x.s > y.s;}int main() { int n; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d %d", &a[i].v, &a[i].s); sort(a, a + n, cmp); long long sum = 0, maxn = 0; for(int i = 0; i < n; i++) { sum += a[i].v; while(q.size() >= a[i].s) { int b = q.top(); q.pop(); sum -= b; } q.push(a[i].v); if(sum > maxn) maxn = sum; } printf("%lld\n", maxn); return 0;}

转载于:https://www.cnblogs.com/fanshhh/p/11407965.html

你可能感兴趣的文章