#include <cstdio> #include <cstring> #include <cmath> #include <map> #include <set> #include <vector> #include <iostream> #include <algorithm> using namespace std; #define N 100005 struct st { long long x,y; }a[N]; long long a1[N],a2[N]; bool cmp(const struct st &a,const struct st &b)//与要排序的变量类型一致 { return a.x<b.x; } int main() { freopen("a","r",stdin); long long n,c,i; long long f; scanf("%lld%lld%lld",&n,&c,&f); for (i=1;i<=c;i++) scanf("%lld%lld",&a[i].x,&a[i].y); sort(a+1,a+c+1,cmp); if (n==1) { long long j1=-1; for (i=1;i<=c;i++) if (a[i].y<=f) j1=a[i].x; printf("%lld\n",j1); return 0; } multiset<long long>p; long long m,m1; multiset<long long>::iterator it; p.clear(); m=0; for (i=1;i<=c-n/2;i++) if (i<=n/2) { p.insert(a[i].y); m+=a[i].y; a1[i]=m; } else { it=p.end(); it--; m1=*it; if (a[i].y<m1) { m=m-m1+a[i].y; p.erase(it); p.insert(a[i].y); } a1[i]=m; } p.clear(); m=0; multiset<long long>::iterator it1; for (i=c;i>=n/2+1;i--) if (i>=c-n/2+1) { p.insert(a[i].y); m+=a[i].y; a2[i]=m; } else { it1=p.end(); it1--; m1=*it1; if (a[i].y<m1) { m=m-m1+a[i].y; p.erase(it1); p.insert(a[i].y); } a2[i]=m; } long long j=-1; for (i=c-n/2;i>=n/2+1;i--) if (a1[i-1]+a[i].y+a2[i+1]<=f) { j=a[i].x; break; } cout<<j<<endl; return 0; } |
Double click to view unformatted code.