重庆市工程建设信息网新网站,萤火虫网站建设优化,沈阳建设电商网站,基本型电子商务网站牛客网【每日一题】3月25题号#xff1a;NC50439 名称#xff1a; tokitsukaze and Soldier 来源#xff1a;练习赛50-C 链接: link.
来源#xff1a;牛客网
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 524288K#xff0c;其他语言10…
牛客网【每日一题】3月25题号NC50439 名称 tokitsukaze and Soldier 来源练习赛50-C 链接: link.
来源牛客网
时间限制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示例2 输入
3
1 3
2 3
100 1输出
100思路 所求的最大战斗力由v和s这两个因素限制。 结构体数组a存放v和s然后对其排序先按照s从大到小如果s相同再排v也是从大到小先要保证足够的人数后面好进行取舍。 定义一个从小到大的优先队列qans相互跟随qq每次添加一个战力值同时用ans加上战力值ans删去q也弹出战力值的先后加入由s的排序决定当q的元素数量大于当前s的值时s是由大到小的排序的就将多出的部分pop出q是从小到大排序所以弹出的总是其中最小值再用ans减去这样ans的值即为在人数限定在s内的最佳情况因为弹出的是最小值相对于前s个数的和所以之后也不用再考虑被弹出的数记录ans的最大值 我刚开始提交是70多分想了一阵子才发现是数组开小了笑哭
#includemap
#includequeue
#includebits/stdc.h
#define maxn 100004
using namespace std;
struct node{long long int v,s;
};
node a[maxn];
bool cmp(node a,node b)
{if(a.s!b.s)return a.sb.s;else return a.va.v;
}
int main()
{int n;cinn;for(int i1;in;i){cina[i].va[i].s;}sort (a1,a1n,cmp);
// int tot0;long long int ans0;int minnmaxn;long long int maxx0;priority_queueint,vectorint,greaterint q;for(int i1;in;i){q.push(a[i].v);ansa[i].v;while(q.size()a[i].s){ans-q.top();
// printf(q.size%d,a[i].s%d,ans%d\n,q.size(),a[i].s,ans);q.pop();
// tot--;}if(ansmaxx)maxxans;}coutmaxx;return 0;
}
