admin 管理员组

文章数量: 887021

战争

战争

问题描述

高老大要打团战了。
他要召集 N （N 是奇数）个人去组织一场战争。
现在高老大的手下有 T 个人，每个人都有一个战斗力值和影响力值。
当这 N 个人的影响力值之和超过 M 的时候，必然会引起巨大的社会动荡。
为了爱与和平，老大明智地决定，不引起巨大的社会动荡。
同时，英明的老大发现，一个团队整体能力等于这 N 个人的战斗力的中位数，中位数越高则战斗力越强。
现在老大想知道，这 N 个人的团队整体能力最大为多少。

输入

输入文件名为War.in。
输入第一行为三个正整数 N， T ，M，意义如上述。
后接 T 行，每行两个正整数 Wi 和 Vi ，代表每个人的战斗力值和影响力值。

输出

输出文件名为War.out。
输出一行一个整数，代表这 N 个人的团队最大的整体能力。无解输出 −1。

输入样例

3 5 70
30 25
50 21
20 20
5 18
35 30

输出样例

35

样例解释

选第 2 、4、 5 个人，影响力 21+18+30=69<=70 ,同时该团队的整体能力为最高的 35 。

数据范围

对于30%的数据，保证T<=200。
对于100%的数据，保证T<=100000，N<=20000每个人的影响力值<=100000，M<= 231−1 .

Solution

把每个人按照战斗力值进行排序，那么枚举中位数，对于第 i 个人，我们只需要求出 1~ i−1 中影响力值最小的 n/2 个人之和， i+1 ~ n 中影响力值最大的 n/2 个人之和。
若它们之和再加上当前人的影响力值小于等于 m ，就可以更新最大值。
如何求区间内的前 k 大的数之和呢？
我们建一个大根堆，每次比较当前数字与堆顶元素的大小关系，若比堆顶元素大，则不管；若比堆顶元素小，则取出堆顶元素，放入当前数字，然后更新和。
时间复杂度 O(nLogn) 。

Code

#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>#define LL long long
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))using namespace std;priority_queue<int,vector<int>,less<int> >q1;
priority_queue<int,vector<int>,less<int> >q2;struct Data{int w,v;
}data[100010];LL n,T,m,ans=-1,sum=0;
LL w[100010],v[100010];
LL sum1[100010];
LL sum2[100010];bool cmp(Data x,Data y){return x.w<y.w;
}int main(){freopen("war.in","r",stdin);freopen("war.out","w",stdout);scanf("%lld%lld%lld",&n,&T,&m);for(int i=1;i<=T;i++){scanf("%d%d",&data[i].w,&data[i].v);}sort(data+1,data+T+1,cmp);for(int i=1;i<=(n>>1);i++){q1.push(data[i].v);sum1[i]=sum1[i-1]+data[i].v;}sum1[n/2+1]=sum1[n/2];for(int i=n/2+2;i<=T;i++){sum1[i]=sum1[i-1];if(q1.top()>data[i-1].v){sum1[i]=sum1[i-1]-q1.top()+data[i-1].v;q1.pop();q1.push(data[i-1].v);}}for(int i=T;i>=T-(n>>1)+1;i--){q2.push(data[i].v);sum2[i]=sum2[i+1]+data[i].v;}sum2[T-(n>>1)]=sum2[T-(n>>1)+1];for(int i=T-(n>>1)-1;i>=1;i--){sum2[i]=sum2[i+1];if(q2.top()>data[i+1].v){sum2[i]=sum2[i+1]-q2.top()+data[i+1].v;q2.pop();q2.push(data[i+1].v);}}for(int i=(n>>1)+1;i<=T-(n>>1);i++){if(sum1[i]+sum2[i]+data[i].v<=m){ans=Max(ans,data[i].w);}}printf("%d\n",ans);return 0;
}

本文标签： 战争

版权声明：本文标题：战争 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1688099065h179127.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。