POJ-2370: Democracy in danger

keyword

greedy　C++

問題概要

K個のグループがある。各グループについて過半数のメンバーが賛成すればそのグループ全体の意見は賛成となる。K個のグループのうち過半数が賛成すれば全体で賛成となる。全体で賛成となるために最小何人必要か求める問題。

解法

各グループに対して必要な人数を求め、小さい順に過半数個選んで和をとればよい。やるだけ。計算量O(K log K)。

#include <cstdio>
#include <algorithm>
#include <numeric>
using namespace std;

const int MAX_K = 109;
int K;
int as[MAX_K];

int solve(){
	for(int i=0; i<K; i++){
		as[i] = as[i]/2+1;
	}
	sort(as, as+K);
	return accumulate(as, as+(K/2+1), 0);
}

int main(){
	scanf("%d",&K);
	for(int i=0; i<K; i++){
		scanf("%d",as+i);
	}
	printf("%d\n", solve());
	return 0;
}