题意的话，就看其他人的吧
概括：二分中位数大体上便是二分一个中位数，带入检验，若分数比他小的有⌊n/2⌋个，分数比他的大的也有这么多，而且贪心的买，花费小于预算。
便带入到数作为中位数是可以的。记录并进行下一次二分
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using std::sort;
const int maxn=101000;
struct node
{
int id;
long long score;
long long cost;
node ( ) { id=score=cost=0; }
};
node base[maxn],pas[maxn];
int rank[maxn];
long long n,c,f;
int compare1(const node &a,const node &b)
{
if(a.score!=b.score) return a.score<b.score;
return a.cost<b.cost;
}
int compare2(const node &a,const node &b)
{
return a.cost<b.cost;
}
int mk_it(int v)
{
long long T1=0,T2=0,Tot=base[v].cost;
for(int i=1;i<=c&&Tot<=f&&T1+T2+1<n;i++)
{
int Id=pas[i].id,F=0;
if(Id==base[v].id) continue;
if((rank[Id]<rank[base[v].id]||pas[i].score==base[v].score)&&T1<(n>>1))
{
++T1;F=1;
Tot+=pas[i].cost;
}
if((rank[Id]>rank[base[v].id]||pas[i].score==base[v].score)&&T2<(n>>1)&&!F)
{
++T2;
Tot+=pas[i].cost;
}
}
return T1+T2+1==n&&Tot<=f;
}
int main()
{
scanf("%lld%lld%lld",&n,&c,&f);
for(int i=1;i<=c;i++)
{
scanf("%lld%lld",&base[i].score,&base[i].cost);
base[i].id=i;
}
sort(base+1,base+1+c,compare1);
for(int i=1;i<=c;i++) rank[base[i].id]=i,pas[i]=base[i];
sort(pas+1,pas+1+c,compare2);
int l=1,r=c;
long long ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(mk_it(mid))
ans=base[mid].score,l=mid+1;
else
r=mid-1;
}
printf("%lld",ans);
}
转载于:https://www.cnblogs.com/Lance1ot/p/10226303.html
