雷山网站快速排名,广州专业网站建设有哪些,自己电脑做的网站如何映射到公网,wordpress加字体颜色题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/1080/C 来源#xff1a;牛客网
在一个游戏中#xff0c;tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。 第i个士兵的战力为v[i]#xff0c;团的战力是团内所有士兵的战力之和。 但…题干
链接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代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,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 id0,ll v0):id(id),v(v){}bool operator(const NN b) const {return v b.v;}
};
priority_queueNN pq;//小根堆
int main()
{int n;cinn;for(int i 1; in; i) {scanf(%lld%d,R[i].v,R[i].s);}ll ans 0,tmp 0;sort(R1,Rn1);for(int i 1; in; 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 ;
}
