#include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; struct node { int a,b; }cow[200010]; node cow2[100010]; int n,c; long long f; bool cmp1(node a,node b) { if(a.a<b.a) return true; else if(a.a==b.a) return a.b<b.b; else return false; } bool cmp2(node a,node b) { return a.b<b.b; } bool solve(int x) { int i,k,value=cow[x].a,num1=0,num2=0,num3=0; long long sum=f-cow[x].b; for(i=1;i<=c;i++) { cow2[i].a=cow[i].a; cow2[i].b=cow[i].b; } cow2[x].a=cow2[c].a; cow2[x].b=cow2[c].b; sort(cow2+1,cow2+c,cmp2); for(i=1;i<c;i++) { if(cow2[i].a==value) { sum-=cow2[i].b; num3++; } else if(cow2[i].a<value && num1<n/2 && sum>=cow2[i].b) { sum-=cow2[i].b; num1++; } else if(cow2[i].a>value && num2<n/2 && sum>=cow2[i].b) { sum-=cow2[i].b; num2++; } if(num1+num2+num3>=n-1) return true; } return false; } int main() { int i,j,ans=-1; scanf("%d%d%I64d",&n,&c,&f); for(i=1;i<=c;i++) scanf("%d%d",&cow[i].a,&cow[i].b); sort(cow+1,cow+1+c,cmp1); int l=1,r=c,mi; while(l<=r) { mi=(l+r)/2; if(solve(mi)) { ans=cow[mi].a; l=mi+1; } else r=mi-1; } if(ans!=-1) printf("%d\n",ans); else printf("-1\n"); } |
Double click to view unformatted code.