https://vjudge.net/problem/CodeForces-1251D
#include <bits/stdc++.h> //#include <cmath> //#include <iostream> //#include <unordered_map> #define mem(x,y) memset(x,y,sizeof(x)) #define pb push_back #define INF 0x3f3f3f3f #define ll long long #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; const int N=2e5+9; int n; ll s; struct node { int l,r; }a[N]; bool cmp(node x,node y) { if(x.l==y.l) return x.r<y.r; return x.l>y.l; } bool ch(int mid) { int z=(n+1)/2; ll ts=s; for(int i=1;i<=n;i++) { if(z&&a[i].l<=mid&&a[i].r>=mid) { z--; ts-=mid; } else { ts-=a[i].l; if(z&&a[i].l>=mid) z--;//先取 } } return z==0&&ts>=0; } int main() { FAST_IO; int T; cin>>T; while(T--) { cin>>n>>s; for(int i=1;i<=n;i++) { cin>>a[i].l>>a[i].r; } sort(a+1,a+1+n,cmp); int res=0; int L=0,R=1e9; while(L<=R) { int mid=(L+R)>>1; if(ch(mid)) { res=mid; L=mid+1; } else R=mid-1; } cout<<res<<endl; } return 0; }
