PKU 3040 Allowance

貪欲。valueの条件から価値の低いコインをたくさん使うより高いコインを1枚つかうほうが後で小回りが効くのでよい。最初、Cを超えないように大きい方から取っていって、それでもCより少なかったら価値の小さいほうからC以上になるまで取っていった。
なるべく無駄がでないようなアルゴリズムを考えればすぐに思いついたけど、なんでこれでうまく行くのかちゃんと証明しろ、と言われると厳しい。ちゃんと証明できるようになりたい。貪欲の難しいところはこういうところだと思う。通した後で難易度表見たら9だった。5,6くらいだと思ってたので意外。まえ違う問題で解法わからないなぁ〜と思って難易度表見たら5だったしよくわからない…

int N,C,ans=0;
struct coin{int v,b;};
coin vec[20];
bool comp(coin a,coin b)
{
	return a.v>b.v;
}
int main()
{
	scanf("%d %d",&N,&C);
	for(int i=0;i<N;i++)
	{
		scanf("%d %d",&vec[i].v,&vec[i].b);
		if(vec[i].v>=C)ans+=vec[i].b,vec[i].b=0;
	}
	sort(vec,vec+N,comp);
	for(;;)
	{
		int sum=0;
		int num=INF;
		int used[20];
		memset(used,0,sizeof(used));
		for(int i=0;i<N;i++)
		{
			if(sum>=C)break;
			int r=min((C-sum)/vec[i].v,vec[i].b);
			if(r==0)continue;
			used[i]=r;
			sum+=r*vec[i].v;
		}
		for(int i=N-1;i>=0;i--)
		{
			if(sum>=C)break;
			if(vec[i].b==0)continue;
			int r=min((C-sum-1)/vec[i].v+1,vec[i].b-used[i]);
			if(r==0)continue;
			used[i]+=r;
			sum+=r*vec[i].v;
			num=min(num,vec[i].b/used[i]);
		}
		if(sum<C)break;
		for(int i=0;i<N;i++)if(used[i]!=0)num=min(num,vec[i].b/used[i]);
		for(int i=0;i<N;i++)vec[i].b-=used[i]*num;
		ans+=num;
	}
	printf("%d\n",ans);
	return 0;
}