penguin's compare heights

2 secs 1024 MB

penguin8331

問題

提出

テストケース

解説

次のような問題を考えます
「ペンギンの不幸さの最大値を x 以下にできるか」
この問題は各水槽ごとのペンギンの身長の最低値と各ペンギンがどの水槽に属しているか管理することで $O(N)$ で求められます。

この x を二分探索することでペンギンの不幸さの最大値を最小化することができます。
よって $O(N log N)$ で解くことができます。

xxxxxxxxxx
 
#include <bits/stdc++.h>
using namespace std;
​
int n, m;
vector<long long> a;
bool solve(long long val) {
    vector<long long> x(n, 10000000000000), y(n, -1);
    int c = 0;
    long long p = 0;
    for (int i = 0; i < n; i++) {
        if (i != 0 && a[i] == a[i - 1]) {
            y[i] = y[i - 1] + 1;
            x[y[i]] = min(x[y[i]], a[i]);
        } else {
            while (x[c] < a[i] - val) {
                c++;
            }
            x[c] = min(x[c], a[i]);
            y[i] = c;
        }
        p = max(p, y[i]);
    }
    if (p > m - 1)
        return true;
    else
        return false;
}
int main() {
    cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    long long l = -1, r = 10000000000;
    while (r - l > 1) {
        long long mid = r - (r - l) / 2;
        if (solve(mid))
            l = mid;
        else
            r = mid;
    }
    if (r < 10000000000)
        cout << r << endl;
    else
        cout << -1 << endl;
}