链接https://ac.nowcoder.com/acm/contest/1080/C来源牛客网时间限制C/C 1秒其他语言2秒空间限制C/C 524288K其他语言1048576K64bit 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输入21 22 2输出3示例2输入31 32 3100 1输出100#includeiostream #includeset #includealgorithm using namespace std; struct node { int v, s; }a[100008]; bool comp(node a,node b) { return a.s b.s; } int main() { multisetint S; int n; long long ans 0, sum 0; cin n; for (int i 0; i n; i) { cin a[i].v a[i].s; } sort(a, a n, comp); for (int i 0; i n; i) { S.insert(a[i].v); sum a[i].v; while (S.size() a[i].s) { sum - *S.begin(); S.erase(S.begin()); } ans max(ans, sum); } cout ans; return 0; }#includeiostream #includealgorithm #includequeue using namespace std; struct node { int x, y; }a[100008]; bool comp(node u, node v) { return u.y v.y; } int main() { priority_queueint,vectorint,greaterint S; int n; long long ans 0, sum 0; cin n; for (int i 0; i n; i) { cin a[i].x a[i].y; } sort(a, a n, comp); for (int i 0; i n; i) { S.push(a[i].x); sum a[i].x; while (S.size() a[i].y) { sum - S.top(); S.pop(); } ans max(ans, sum); } cout ans; return 0; }#includeiostream #includealgorithm #includequeue using namespace std; struct node { int x, y; bool operator(const node v)const { return xv.x; } }a[100008]; bool comp(node u, node v) { return u.y v.y; } int main() { priority_queuenode S; int n; long long ans 0, sum 0; cin n; for (int i 0; i n; i) { cin a[i].x a[i].y; } sort(a, a n, comp); for (int i 0; i n; i) { S.push(a[i]); sum a[i].x; while (S.size() a[i].y) { sum - S.top().x; S.pop(); } ans max(ans, sum); } cout ans; return 0; }#includeiostream #includealgorithm #includequeue using namespace std; struct node { int x, y; }a[100008]; bool comp(node u, node v) { return u.y v.y; } struct cmp1 { bool operator()(const node u, const node v)const { return u.x v.x; } }; int main() { priority_queuenode,vectornode,cmp1 S; int n; long long ans 0, sum 0; cin n; for (int i 0; i n; i) { cin a[i].x a[i].y; } sort(a, a n, comp); for (int i 0; i n; i) { S.push(a[i]); sum a[i].x; while (S.size() a[i].y) { sum - S.top().x; S.pop(); } ans max(ans, sum); } cout ans; return 0; }第一个程序用multiset容器默认从小到大排序。第二个程序用priority_queue,其默认为大根堆这里通过priority_queueint,vector,greater S改为小根堆。默认的大根堆参数为priority_queueint,vector,less S.另外这里的数据类型是基本数据类型。第三个程序的数据类型是自定义的结构体可以采用程序中的方法定义小根堆重载。第四个程序是将定义小根堆的方法写在了结构体外面 重载() )。