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