kojingharangの日記

GCJ2012 Qualification B. Dancing With the Googlers

10:55 |

• 数字３つの tuple の合計値が N 個与えられる。N 個の元の tuple のうち、tuple の最大値 max, 最小値 min として max - min == 2 なのが S 個(surprisingと呼ぶ)、残りは max-min < 2 のとき、
• 最大値が p 以上のものの数の最大値を求める問題。

• 合計値が x のとき、surprising なら最大値は (x+2)/3, そうじゃなければ (x+4)/3 と一意に決まる
• ので、合計値を降順にソートして greedy に処理する。
• 全部 not surprising としておいて、p 以上のはそのままカウント
• 超えてないもので surprising とすれば p 以上になるものは surprising 券がまだ使えるならカウント

int main() {
	int test_cases;
	cin>>test_cases;
	REP(ttt, test_cases) {
		int N, S, P;
		cin>>N>>S>>P;
		VI T(N);
		REP(i, N) cin>>T[i];
		sort(ALLR(T));
		//cout<<T<<endl;
		int ans = 0;
		REP(i, N) {
			if((T[i]+2)/3 >= P) ans++;
			else if(S>0 && T[i]>=2 && (T[i]+4)/3 >= P) {
				ans++;
				S--;
			}
		}
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

ツイートする