tokitsukaze and Soldier

朱雀 2023-03-12 09:12 12阅读 0赞

链接：[传送门][Link 1]  
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒  
空间限制：C/C++ 524288K，其他语言1048576K  
64bit IO Format: %lld  
题目描述  
在一个游戏中，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  
输入  
复制  
2  
1 2  
2 2  
输出  
复制  
3  
解题思路：先将每个士兵按照人数限制从大到小排序（即贪心），然后找出当前最优战力与历史最优战力进行比较。  
数据较大，要用龙龙。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    struct node
    { 
        ll v ,s;
        bool operator <(const node & y) const
        { 
            return s>y.s;//人数大的排前面
        }
    }a[100005];
    int main()
    { 
        ll sum=0,n,ans=0,i;
        priority_queue <ll,vector<ll>,greater<ll> > p;//使用优先队列存储士兵的战力值,小顶队列
        cin>>n;
        for(i=1;i<=n;i++)
            cin>>a[i].v>>a[i].s;
        sort(a+1,a+1+n);
        for(i=1;i<=n;i++)
        { 
           sum+=a[i].v;//记录此次探索的值
    		p.push(a[i].v);
           while(p.size()>a[i].s)
           { 
               sum-=p.top();//记录此次探索后的值，sum是本次最优，而ans是历史最优
               p.pop();
           }
            ans=max(ans,sum);	
        }
        cout<<ans;
        return 0;
    }```

[Link 1]: https://ac.nowcoder.com/acm/contest/1080/C