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}\) 都进行这样的操作就可以了。

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

• 因为除数不能为 \(0\)，所以当 \(a_{i}=a_{i+1}\) 时，直接将 \(ans_{i}\) 赋值为 \(ans_{i-1}\) 就可以了。

• 根据题目定义，显然 \(ans_{i+1}\) 不可能大于 \(ans_{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;
}