[GDCPC2023] New Houses 题解

Zaku · 2023-10-07 19:29:40 · 题解

Link.

为了使问题简单化，我们首先假设所有人都没有邻居。

然后考虑 i 有了邻居，他的满意度会增加 (a_i - b_i)。

所以将 (a_i - b_i) 从大到小排序，并考虑 k 个人有邻居时的总满意度。

我们首先要考虑所有人都没有邻居，即 k=0 的情况。请注意，只有 2n-1\le m 时才有这种可能，否则房子就不够了。此时总满意度为 t。

然后考虑 k 个人有邻居时的情况。这时只有 2n-k \le m 才能考虑。理由同上。这时我们假设有邻居的人都住在左边，没邻居的都隔着一栋房子住在右边。如图。

此时总满意度是 t+{\sum\limits_{i=1}^{k}}(a_i-b_i)。

最后在 k=2,3,\cdots n 的情况中取 \max 即可。

希望没有人提出 k 为什么不能等于 1。

时间复杂度 \mathcal{O}(n\log n)。

const int N = 5e5 + 5;
int a[N], b[N], c[N];
void solve(){
    int n, m;
    cin >> n >> m;
    ll t = 0;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i] >> b[i];
        t += b[i];
    }
    for (int i = 1; i <= n; i ++ )
        c[i] = a[i] - b[i];
    sort (c + 1, c + 1 + n, greater<int>());
    ll ans = 0;
    if (2 * n - 1 <= m) 
        ans = t;
    t += c[1];
    for (int k = 2; k <= n; k ++ ){
        t += c[k];
        if (2 * n - k <= m)
            ans = max(ans, t);
    }
    cout << ans << '\n';
}