GCJ2012 Round 1A : Kingdom Rush

問題概要

A[i] <= B[i]な配列が与えられる。S=0からスタートして、iを選びB[i]<=Sなら1点Sに加算し、A[i]<=Sなら1点加算される。ただし得点獲得の機会は一度しかなく、B[i]<=SならA[i]の分もSに加算される。iを選ぶ回数を最小化する問題。

解法

貪欲に選ぶ。S>=B[i]なiがあればそれをクリアし、なければS>=A[i]なiのうちBが最大のものを選べばよい。heapを使えばN*log Nで解けそうな気もするけどN<1000なんだから愚直にN^2で十分。余計なことをする必要はない。

acceptされたコード

import std.stdio, std.algorithm;
import std.conv;

int N;
int[] as, bs;

void init(){
	scanf("%d", &N);
	as = new int[](N);
	bs = new int[](N);
	foreach(i; 0..N){
		scanf("%d%d", &as[i], &bs[i]);
	}
}

string solve(){
	int ans = 0;
	int curStar = 0;
	
	for(;;){
		int mini = int.max, key = -1;
		foreach(i; 0..N){
			if(bs[i] < mini){
				mini = bs[i];
				key = i;
			}
		}
		if(key == -1){
			break;
		}
		
		
		if(mini <= curStar){
			++ans;
			curStar += as[key] == int.max ? 1 : 2;
			as[key] = bs[key] = int.max;
			continue;
		}
		
		int maxi = -1;
		key = -1;
		foreach(i; 0..N){
			if(as[i] <= curStar && maxi < bs[i]){
				maxi = bs[i];
				key = i;
			}
		}
		
		if(key == -1){
			return "Too Bad";
		}
		
		++ans;
		curStar += 1;
		as[key] = int.max;
	}
	
	return to!string(ans);
}

void main(){
	int T;
	scanf("%d", &T);
	foreach(c; 0..T){
		init;
		writefln("Case #%d: %s", c+1, solve);
	}
}