kojingharangの日記

Codeforces Round #129 Div1 B - Little Elephant and Cards

22:48 |

• 10^5 個までの表を向いたカードがあって表裏にそれぞれ 10^9 までの整数が書いてある。
• カードの半分以上が同じ数字になるようにするには最小で何枚ひっくり返せばいいか。

• 半分以上揃う数字はせいぜい 4 つくらいしかない
• map で出現個数を数えて、あてはまるものについて「全体の半分 - すでに表をむいてる枚数」の最小を求める。
• 表裏同じ数字の場合は１回だけカウントするところで 1WA
• 表の枚数も map で数えたが count(ALL(F), c) でも大丈夫だと思う

• Accepted

#define INF (1LL<<60)

int main() {
	ll N;
	while(cin>>N) {
		ll half=(N+1)/2;
		map<ll, ll> hi;
		map<ll, ll> hiF;
		VI F(N), B(N);
		REP(i, N) {
			cin>>F[i]>>B[i];
			hi[F[i]]++;
			if(F[i]!=B[i]) hi[B[i]]++;
			hiF[F[i]]++;
		}
		//cout<<F<<B<<endl;
		//cout<<hi<<endl;
		VI cand;
		FOR(e, hi) {
			if(e->second >= half) cand.PB(e->first);
		}
		//cout<<cand<<endl;
		ll ans = INF;
		REP(i, cand.size()) {
			ll c = cand[i];
			//ll rest = half - count(ALL(F), c);
			ll rest = half - hiF[c];
			ans = min(ans, max(0LL, rest));
		}
		
		cout<<(cand.size() ? ans : -1LL)<<endl;
	}
	
	return 0;
}

ツイートする