[HOJ] 85 - 毛毛蟲問題

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
#define N 300005
struct P{
    long long int x,y;
    friend bool operator < (P a,P b){
        return a.x<b.x;
    }
}s[N];
int cmp(P a,P b){
    return a.y>b.y;
}
long long int sum;
int n;
bool test(int k){
    int i;
    sum=0;
    priority_queue<P> que;
    for(i=0;i<k-1;i++){
        que.push(s[i]);
        sum+=s[i].x;
    }
    que.push(s[i]);
    sum+=s[i].x;
    if(sum<=s[i].y*k) return 1;
    for(i=k;i<n;i++){
        P in=que.top();
        if(in.x>s[i].x){
            que.pop();
            que.push(s[i]);
            sum-=in.x;
            sum+=s[i].x;
        }//printf("%lld,,%lld,,%lld\n",in.x,sum,s[i].x);
        if(sum<=s[i].y*k) return 1;
    }
    return 0;
}
int main(){
    int i,j,ans=0,l,r,m;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%lld%lld",&s[i].x,&s[i].y);
        if(s[i].x<=s[i].y) ans=1;
    }
    if(!ans){
        puts("0");
        return 0;
    }
    sort(s,s+n,cmp);
    l=1,r=n+1;
    while(l+1!=r){
        m=(l+r)/2;
        if(test(m)) l=m;
        else r=m;
    }
    //printf("%d..",test(3));
    printf("%d\n",l);
}