Prefix Purchase 题解

· · 题解

题意

给定一个长度为 n 的序列 ans，初始值全部为 0。你一共有 k 个硬币，你可以选择花 a_{i} 个硬币来使 ans_{1} 到 ans_{i} 中的所有数加一。求最终能得到的 ans 序列中字典序最大的一个。

思路

首先我们可以发现一个很显然的性质：如果满足 a_{i}>a_{i+1} 的话，那么选 i+1 位置一定比选 i 位置更优。所以我们就可以先将 a_{i} 赋值为 \min(a_{i},a_{i+1})，这样就可以避免掉上面所说的这种情况了。

又因为题目要求最终序列的字典序最大（靠前的数字最大），所以我们肯定要贪心的去先选前面的，即从 a_{1} 开始选。但是我们会发现选完 a_{1} 之后 k 还会剩下一些，如果直接不管的话肯定不是最优的。所以我们就可以用 k 剩下的这些值去将一些选 a_{1} 的变成选 a_{2} 的，且个数不变，这样既可以保证当前的字典序不变（选 1 的个数没变），还可以让后面的字典序变大（选 2 的个数变多）。那么这样操作一定是更优的。那么就可以算出选 a_{2} 的数量就应该是：(k-k \div a_{1} \times a_{1}) \div (a_{2}-a_{1})。意思是用 k 剩下的值除以每一次变化需要的代价。然后对于每一个 a_{i} 都进行这样的操作就可以了。

但是这里有几个点需要注意：

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
#define inf_db 127
#define ls id << 1
#define rs id << 1 | 1
#define re register
#define endl '\n'
typedef pair <int,int> pii;
const int MAXN = 2e5 + 10;
int T,n,k,mn = 1e18,a[MAXN],ans[MAXN];
signed main()
{
    cin >> T;
    while(T--)
    {
        cin >> n;
        mn = ans[0] = 1e18;
        for(int i = 1;i <= n;i++) cin >> a[i];
        for(int i = n;i >= 1;i--) mn = min(mn,a[i]),a[i] = mn; 
        cin >> k;
        for(int i = 1;i <= n;i++)
        {
            if(a[i] - a[i - 1] == 0) ans[i] = ans[i - 1];
            else ans[i] = min(k / (a[i] - a[i - 1]),ans[i - 1]);
            cout << ans[i] << " ";
            k -= (a[i] - a[i - 1]) * ans[i];
        }
        cout << endl;
        for(int i = 1;i <= n;i++) ans[i] = 0;
    }
    return 0;
}