Codeforces Round #204 (Div. 1) A. Jeff and Rounding

Codeforces Round #204 (Div. 1) の練習会に参加しました。今回は B < A < C という難易度だった感じがする。

問題

codeforces.com

解法

まず, 各実数の整数部分は関係ないのでそぎ落としましょう。すると, 基本的には ai の床関数を取ることは ai に対応する整数として 0 を取ることに, ai の天井関数を取ることは ai に対応する整数として 1 を取ることになります。ただ例外があって, ai が 0 の場合は, 床関数を取ろうが天井関数を取ろうが ai に対応する整数は 0 を取ることになります。

よって, 各 ai に対応する整数として 1 を取るか 0 を取るかの自由度が ai == 0 となる小数の数分だけ出来てこれについて「整数部分の和」と「小数部分の和」の差の絶対値を最小化しよう, という問題になります。

ai == 0 となる小数の数(cnt とする)が n 以下の場合, 整数部分の和は実質的に n-cnt から n 個まで取ることが出来ます。
また, cnt > n の場合, 整数部分の和は実質的に 0 から 2*n-cnt 個まで取ることが出来ます。

const int MAXN = 4040;
double A[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int cnt = 0;
    double sum = 0;
    for (int i = 0; i < 2*n; i++) {
        cin >> A[i];
        double tmp, y;
        y = modf(A[i], &tmp);
        if (y == 0) cnt++;
        sum += y;
    }
    if (cnt <= n) {
        double ans = 1e9;
        for (int i = n-cnt; i <= n; i++) {
            ans = min(ans, abs(sum-i));
        }
        printf("%.3lf\n", ans);
    } else {
        double ans = 1e9;
        int a, b;
        for (int i = 0; i <= 2*n-cnt; i++) {
            ans = min(ans, abs(sum-i));
        }
        printf("%.3lf\n", ans);
    }
    return 0;
}