题目描述

难度分:$1800$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$c(1 \leq c[i] \leq 10^9)$。

然后输入$k(1 \leq k \leq 10^9)$。

你有$k$块钱和一个长为$n$的全$0$数组$a$。每次操作，你可以花费$c[i]$，把前缀$a[1],…,a[i]$都加一，前提是$c[i] \leq k$。输出你能得到的字典序最大的$a$。

输入样例

4
3
1 2 3
5
2
3 4
7
3
3 2 1
2
6
10 6 4 6 3 4
7

输出样例

5 0 0 
2 1 
2 2 2 
2 2 2 2 2 1 

算法

反悔贪心

感觉这种贪心题真的好难，反悔贪心WA了好久都搞不清错在哪了，打了这里的补丁又错了那里。

首先比较容易发现的一点是如果$a[i] \geq a[i+1]$，那$a[i]$就肯定没有必要选，因为选择后面的$i+1$可以让更长的前缀加$1$，还花费更小。所以先原地预处理一个$c$的后缀最小值数组，此时$c$就是单调不减的了。

然后正序遍历$i \in [1,n]$开始贪心：

1. 如果$i=1$，令$a[1]=\lfloor \frac{k}{c[1]} \rfloor$（$\lfloor . \rfloor$表示对$.$向下取整），这时候$k$减少$a[1] \times c[1]$。

2. 对于$i \gt 1$的情况，我们开始反悔，因为存在这样的情况，在前面$j$位置可以加$t$次，但是把前面的花费剩下来，选择当前位置的$c[i]$也可以加$t$次，这样不仅不会让前面的$a[j]$减小，反而让后面多加了几个数，字典序更大。目的是让$a[j]$不变的前提下$k + cnt \times c[j]=cnt \times c[i]$，$a[i]$最大，所以能变就变，$cnt=a[i]=\lfloor \frac{k}{c[i]-c[j]} \rfloor$。分母有可能为$0$，此时要把$i$上的操作转移到$i+1$，直接令$a[i+1]=a[i]$。除此之外，$i-1$位置可能也不够$\lfloor \frac{k}{c[i]-c[j]} \rfloor$次让你返悔，所以$a[i]=min(a[i-1],\lfloor \frac{k}{c[i]-c[j]} \rfloor)$。

复杂度分析

时间复杂度

预处理出$c$的后缀最小值数组时间复杂度为$O(n)$，之后遍历$i \in [1,n]$求答案时间复杂度还是$O(n)$。因此，整个算法的时间复杂度为$O(n)$。

空间复杂度

除了输入的数组$c$，还开辟了答案数组$a$的空间，额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;
int t, n, k, c[N], a[N];

int main() {
    scanf("%d", &t);
    for(int cases = 1; cases <= t; cases++) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &c[i]);
        }
        for(int i = n - 1; i >= 1; i--) {
            c[i] = min(c[i], c[i + 1]);
        }
        scanf("%d", &k);
        for(int i = 1; i <= n; i++) {
            if(c[i] == c[i - 1]) {
                a[i] = a[i - 1];
            }else {
                a[i] = min(k / (c[i] - c[i - 1]), i != 1? a[i - 1] : 0x3f3f3f3f);
                k -= (c[i] - c[i - 1]) * a[i];
            }
            printf("%d%c", a[i], " \n"[i == n]);
        }
    }
    return 0;
}