D. Prefix Purchase
You have an array $a$ of size $n$, initially filled with zeros ($a_1 = a_2 = \ldots = a_n = 0$). You also have an array of integers $c$ of size $n$.
Initially, you have $k$ coins. By paying $c_i$ coins, you can add $1$ to all elements of the array $a$ from the first to the $i$-th element ($a_j \mathrel{+}= 1$ for all $1 \leq j \leq i$). You can buy any $c_i$ any number of times. A purchase is only possible if $k \geq c_i$, meaning that at any moment $k \geq 0$ must hold true.
Find the lexicographically largest array $a$ that can be obtained.
An array $a$ is lexicographically smaller than an array $b$ of the same length if and only if in the first position where $a$ and $b$ differ, the element in array $a$ is smaller than the corresponding element in $b$.
Input
The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. This is followed by a description of the test cases.
The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the size of arrays $a$ and $c$.
The second line of each test case contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq 10^9$) — the array $c$.
The third line of each test case contains a single integer $k$ ($1 \leq k \leq 10^9$) — the number of coins you have.
It is guaranteed that the sum of all $n$ values across all test cases does not exceed $2 \cdot 10^5$.
Output
For each test case, output $n$ integers $a_1, a_2, \ldots, a_n$ — the lexicographically largest array $a$ that can be obtained.
Example
input
4 3 1 2 3 5 2 3 4 7 3 3 2 1 2 6 10 6 4 6 3 4 7
output
5 0 0 2 1 2 2 2 2 2 2 2 2 1
Note
In the first test case, $a_1$ cannot be greater than $5$, and if we buy $c_1$ five times, we will run out of money, so $a = [5, 0, 0]$.
In the second test case, $a_1$ cannot be greater than $2$, but we can buy $c_1$ and $c_2$ once each (buying $c_2$ twice is not possible), so $a = [2, 1]$.
解题思路
如果有下标 $i < j$,并且 $c_i \geq c_j$,那么很明显买入 $c_j$ 要比 $c_i$ 更优,因为不仅前缀的长度 $j$ 比 $i$ 大,而且价格也不超过 $c_i$。因此要把所有这样的 $c_i$ 删掉,有点类似于单调栈,最后栈内的元素(存的是下标)是严格递增的,满足 $i < j$,则 $c_i < c_j$。
然后就是贪心地选择栈内的哪些元素购买,使得序列 $a$ 的字典序最大,这步卡了我很久。设栈的大小为 $sz$,栈底元素是 $\text{stk}[1]$,由于栈底元素对应的 $c_{\text{stk}[1]}$ 最小,因此要使得 $a$ 的前 $\text{stk}[1]$ 个元素字典序最大,那么在下标 $\text{stk}[1]$ 处最多能买入 $\left\lfloor \dfrac{k}{c_{\text{stk}[1]}} \right\rfloor$ 次。对于前 $\text{stk}[1]$ 个元素而言这是上界,否则如果在其他位置 $\text{stk}[i], \, i \in [2,sz]$ 买入,那么字典序肯定不如这个上界大,因为 $c_{\text{stk}[i]} > c_{\text{stk}[1]}, \, \left\lfloor \dfrac{k}{c_{\text{stk}[i]}} \right\rfloor < \left\lfloor \dfrac{k}{c_{\text{stk}[1]}} \right\rfloor$。
买入后会有剩余,记作 $k' = k \bmod c_{\text{stk}[1]}$,在保持 $a$ 的前 $\text{stk}[1]$ 个元素字典序最大的前提下,看看能不能买入其他的 $\text{stk}[i]$ 来替换 $\text{stk}[1]$,使得字典序更大。对于 $\text{stk}[2]$ 的话,如果想要用 $\text{stk}[1]$ 替换,那么需要 $c_{\text{stk}[2]} - c_{\text{stk}[1]}$ 的花费,而最多可以替换 $\left\lfloor \dfrac{k'}{c_{\text{stk}[2]} - c_{\text{stk}[1]}} \right\rfloor$ 次。另外还要考虑到在 $\text{stk}[1]$ 买入的次数 $a_{\text{stk}[1]}$,即替换的次数不能超过这个值,因此实际上最多能替换 $\min \left\{ a_{\text{stk}[1]}, \, \left\lfloor \dfrac{k'}{c_{\text{stk}[2]} - c_{\text{stk}[1]}} \right\rfloor \right\}$ 次。
记剩余的 $k'' = k' \bmod c_{\text{stk}[2]} - c_{\text{stk}[1]}$,同理对于 $\text{stk}[3]$,我们应该用 $\text{stk[2]}$ 来替换 $\min \left\{ a_{\text{stk}[2]}, \, \left\lfloor \dfrac{k''}{c_{\text{stk}[3]} - c_{\text{stk}[2]}} \right\rfloor \right\}$ 次。而不用再考虑用 $\text{stk}[1]$ 来替换,这是因为将 $\text{stk}[1]$ 替换成 $\text{stk}[3]$,等价于先将 $\text{stk}[1]$ 替换成 $\text{stk}[2]$,再将 $\text{stk}[2]$ 替换成 $\text{stk}[3]$,两种替换方式的花费是一样的。而上一步已经通过最大次数来将 $\text{stk}[1]$ 替换成 $\text{stk}[2]$,以使得 $a$ 的字典序尽可能大,因此 $k''$ 是无法再将 $\text{stk}[1]$ 替换成 $\text{stk}[2]$,因此不足以将 $\text{stk}[1]$ 替换成 $\text{stk}[3]$。
以此类推,可以发现每一次只需将前一个元素替换即可。
AC 代码如下,时间复杂度为 $O(n)$:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 6 const int N = 2e5 + 10; 7 8 int a[N]; 9 int stk[N], tp; 10 int ans[N]; 11 12 void solve() { 13 int n, m; 14 scanf("%d", &n); 15 tp = 0; 16 for (int i = 1; i <= n; i++) { 17 scanf("%d", a + i); 18 while (tp && a[i] <= a[stk[tp]]) { // 删掉下标小于i且花费大于等于a[i]的元素 19 tp--; 20 } 21 stk[++tp] = i; // 栈里存的是下标 22 } 23 scanf("%d", &m); 24 memset(ans, 0, n + 10 << 2); 25 ans[0] = 2e9; 26 for (int i = 1; i <= tp; i++) { 27 int t = min(ans[stk[i - 1]], m / (a[stk[i]] - a[stk[i - 1]])); // 最多替换的次数 28 ans[stk[i]] = t; 29 ans[stk[i - 1]] -= t; 30 m -= t * (a[stk[i]] - a[stk[i - 1]]); 31 } 32 for (int i = n; i; i--) { 33 ans[i] += ans[i + 1]; 34 } 35 for (int i = 1; i <= n; i++) { 36 printf("%d ", ans[i]); 37 } 38 printf("\n"); 39 } 40 41 int main() { 42 int t; 43 scanf("%d", &t); 44 while (t--) { 45 solve(); 46 } 47 48 return 0; 49 }
参考资料
CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) Editorial:https://codeforces.com/blog/entry/120524