題干：

鏈接：https://ac.nowcoder.com/acm/contest/1080/C
來源：牛客網
?

在一個游戲中，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

示例2

輸入

復制

3 1 3 2 3 100 1

輸出

復制

100

解題報告：

按s排個序，然后貪心選就行了，優先隊列維護前s[i]大元素。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; struct Node {int s;ll v;bool operator<(const Node & b) const {return s > b.s;//按照人數從大到小排序 } } R[MAX]; struct NN {int id;ll v;NN(int id=0,ll v=0):id(id),v(v){}bool operator<(const NN & b) const {return v > b.v;} }; priority_queue<NN> pq;//小根堆 int main() {int n;cin>>n;for(int i = 1; i<=n; i++) {scanf("%lld%d",&R[i].v,&R[i].s);}ll ans = 0,tmp = 0;sort(R+1,R+n+1);for(int i = 1; i<=n; i++) {tmp += R[i].v; pq.push(NN(i,R[i].v));while(pq.size() > R[i].s) {NN cur = pq.top();pq.pop();tmp -= cur.v;}ans = max(ans,tmp);}printf("%lld\n",ans);return 0 ; }

?

總結

以上是生活随笔為你收集整理的【牛客 - 1080C】tokitsukaze and Soldier（思维，偏序问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。