B. Kingdom Rush

2012-04-28

02:01 |

レベルNまでの面があって各面を星１or２でクリアすることができる。各面に対して星１or２でクリアするに当たって必要な所持星数がきまってる。全面を星２でクリアするには最低何回クリアすればいいか。

星２の必要星数が少ない順にクリアする。その際、所持星数が足りない場合は星１をクリアすることになる
当初、星１の必要星数が少ない順でいいかと思ってたけどsmall通らず。
しばらくやってわからないのでギブアップして解説をみると、条件を満たす星１の中で星２の必要星数が多い順にクリアするといいらしい
例えば (0 1) (0 3) のとき、面１星１→面１星２ではダメで面２星１→面１星２→面２星２でクリアする必要がある

想定アルゴリズムが間違ってるっぽい時は、手動で反例を探すか全探索での答えと一致するかチェックしないといけないな...

int f(int N, vector<PII>& a, vector<PII>& b) {
	VI lvl(N);
//	sort(ALL(a));
	sort(ALL(b));
	int cur=0;
	int ok=1;
	int ans=0;
	REP(i, N) {
		REP(ai, N) {
			if(cur >= b[i].first) break;
			// find appropriate star1
			int idx=-1, maxb=-1;
			REP(j, N) {
				if(cur >= a[j].first && lvl[j]==0 && maxb < a[j].second) {
					idx=j;
					maxb = a[j].second;
				}
			}
			if(idx!=-1) {
				cur++;
				lvl[idx]=1;
//				cout<<"use 1 in "<<a[ai].first<<" "<<b[i].first<<endl;
				ans++;
			} else break;
		}
		if(cur < b[i].first) { ok=0; break; }
		cur+=lvl[b[i].second]==1 ? 1 : 2;
		lvl[b[i].second]=2;
	}
	return ok?N+ans:-1;
}

int main() {
	int test_cases;
	cin>>test_cases;
	REP(ttt, test_cases) {
		int N;
		cin>>N;
		vector<PII> a(N), b(N);
		REP(i, N) {
			cin>>a[i].first>>b[i].first;
			a[i].second = b[i].first;
			b[i].second=i;
		}
		int F = f(N, a, b);
//		int Ref = ref(N, a, b);
//		if(F!=Ref) {
//			cout<<"DIFF Case #"<<ttt+1<<" "<<F<<" "<<Ref<<endl;
//		}
		if(F!=-1) cout<<"Case #"<<ttt+1<<": "<<F<<endl;
		else cout<<"Case #"<<ttt+1<<": Too Bad"<<endl;
	}
	return 0;
}