JOI2011本選5番
kについて二分探索した後、その判定を頑張ってO(n)で出来るようにする。
#include <stdio.h> #include <utility> #include <set> #include <algorithm> #include <vector> #define MAX_V 1000100 using namespace std; int n; int ai[MAX_V],can[MAX_V],bi2ai[MAX_V]; pair<int,int> bi[MAX_V]; int ok(int k) { if(k==0) return 1; double sumA=0; for(int i=0;i<n;i++) can[i]=1; for(int i=0;i<k;i++) sumA+=ai[i]; int lastA=k-1; for(int b=0;b+k<=n;b++) { if(sumA/(double)k<=(double)bi[b].first) return 1; int tP=bi2ai[b]; can[tP]=0; if(tP<=lastA) { sumA-=ai[tP]; lastA++; if(lastA>=n) return 0; while(!can[lastA]) lastA++; sumA+=ai[lastA]; } } return 0; } int main() { scanf("%d",&n); for(int i=0;i<n;i++) { int a,b; scanf("%d%d",&a,&b); ai[i]=a; can[i]=1; bi2ai[i]=-1; bi[i]=make_pair(b,-a); } sort(ai,ai+n); sort(bi,bi+n); for(int i=0;i<n;i++) { int a=-bi[i].second; int tB=lower_bound(ai,ai+n,a)-ai; int tE=upper_bound(ai,ai+n,a)-ai; int tP; for(tP=tB;tP<tE;tP++) if(can[tP]) break; can[tP]=0; bi2ai[i]=tP; } int b=0,c=n; while(1<c-b) { int m=(b+c)/2; if(ok(m)) b=m; else c=m; } if(ok(c)) printf("%d\n",c); else printf("%d\n",b); return 0; }