Solution Of CF2032C Trinity

Dr1fty · 2024-11-02 07:34:04 · 题解

Preface

赛场解法和官解写法有一点不一样，发一篇。

Solution

我们注意到本题的要求与下标无关，只与具体的 a_i 的值有关，因此直接考虑排序。

我们对 a 进行升序排序。此时我们考虑枚举每个 a_i(1 \le i < n) 作为修改完后序列的最小值，那么显然次小值即为 a_{i + 1}，此时我们再去算序列中可以存在的最大值，也就是最后一个使得 a_i + a_{i + 1} < a_j 的 j，直接二分查找就好，在 j 之后的 a_k 都直接改成 a_j，而对于在 i 之前的 a_k 也都改成 a_j 就满足了要求。此时对于这个 i 我们共需要 n - j + i - 1 次操作。

那么我们对于每个 i 求操作次数取个 \min，做完了。

时间复杂度 \mathcal{O}(n\log n)，可以通过测试。

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int T; cin >> T;
    for (int n; T --; ) {
        cin >> n;
        vector <int> a(n);
        for (int i = 0; i < n; i ++) cin >> a[i];
        sort (a.begin(), a.end());
        int ans = n - 1;
        for (int i = 0; i + 1 < n; i ++) {
            int x = lower_bound(a.begin(), a.end(), a[i] + a[i + 1]) - a.begin();
            ans = min(n - x + i, ans);
        }
        cout << ans << '\n';
    }
    return 0;
}