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;
}