SRM 544 div1 easy: ElectionFraudDiv1

問題

TopCoder Statistics - Problem Statement

x(1 以上の整数) 人の有権者が n 人の候補者に投票をする。

n 人の票獲得率(a 人から票を獲得した場合 a/x*100 )を四捨五入した一覧が与えられるので, x としてあり得る最小値を求めよ(ない場合は -1)。

解法

1000 程度まで調べて答えがあったら最小値を, なかったら -1 を答えれば良いです。
調べ方ですが, i 番目の人の票獲得数が y で票獲得率が a% の場合,

a-0.5 <= y/x*100 < a+0.5
2*a-1 <= y/x*200 < 2*a+1

が成り立つので, y*200 と (2*a-1)*x, (2*a+1)*x を比べれば「y 票獲得した」という状況があり得るかがわかります。下のコードは O(x^2) かかってますが, 二分探索とか使えばもっと早く出来ます。

1000 程度まで調べれば良い理由は解説に載っています。
http://apps.topcoder.com/wiki/display/tc/SRM+544

vi p;

bool check(int num) {
    int mini = 0, maxi = 0;
    int n = p.size();
    for (int i = 0; i < n; i++) {
        int l = num, r = -1;
        for (int j = 0; j <= num; j++) {
            if ((2*p[i]-1)*num <= j*200 && j*200 < (2*p[i]+1)*num) {
                l = min(l, j), r = max(r, j);
            }
        }
        if (r == -1) return false;
        mini += l, maxi += r;
    }
    return mini <= num && num <= maxi;
}

class ElectionFraudDiv1 {
public:
    int MinimumVoters(vector <int> percentages) {
        p = percentages;
        for (int i = 1; i <= 1000; i++) {
            if (check(i)) return i;
        }
        return -1;
    }
};