CF1904B 题解

yyrwlj · 2023-12-10 14:51:00 · 题解

题目传送门

思路

首先，显然从小到大删除数字是最优的，所以我们再准备一个将原序列 t 升序排序后的 a 序列。

先来看接下来的朴素做法。

所有小于等于当前数的都可以直接删除，所以把 a 序列从前往后扫，一直扫到 a_j > t_i 为止，此时的分数为 \sum_{k=1}^{j}a_k。

然后 k 继续从 j+1 到 n 扫，直到当前的分数小于 a_k 为止。时间复杂度 O(n^2)。

接下来考虑优化

由于 a 序列是单调不减的，所以找到最大的 j 使得 a_j \le t_i 可以使用二分。计算 \sum_{k=1}^{j}a_k 可以预处理前缀和。

然后要找到最小的 k，使得 j \le k \le n 且 \sum_{i=1}^{k}a_k < a_{k+1}。

我们发现不能直接使用二分，因为不满足二段性。

但是可以将所有满足 \sum_{j=1}^{i}a_j < a_{j+1} 的 i 存进一个序列 d 中，我们会发现 d 是单调递增的。

于是问题就转化成了找到一个最小的 k，使得 d_k \ge j，可以使用二分解决，时间复杂度优化成了 O(n \log n)。

注意，因为有可能出现可以删除所有数的情况，所以要把 n 放到 d 的末尾。

Code

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;
int a[N], t[N];
long long s[N];
int d[N];
void work()
{
    int n;
    scanf("%d", &n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d", &t[i]);
        a[i] = t[i];
    }
    sort(a + 1, a + n + 1);
    int m = 0;
    for (int i=1;i<=n;i++)
    {
        s[i] = s[i - 1] + a[i];
        if (s[i] < a[i + 1])
            d[++m] = i;
    }
    d[++m] = n;
    for (int i=1;i<=n;i++)
    {
        int l = 1, r = n, ans;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (a[mid] <= t[i])
                l = mid + 1, ans = mid;
            else
                r = mid - 1;
        }
        if (ans == 1)
        {
            printf("0 ");
            continue;
        }
        l = 1, r = m;
        int ans2 = m;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (d[mid] >= ans)
                r = mid - 1, ans2 = mid;
            else
                l = mid + 1;
        }
        printf("%d ", d[ans2] - 1); //减一是因为要排除自己
    }
    putchar('\n');
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        work();
    return 0;
}