D. Prefix Purchase CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)

Problem - D - Codeforces

题目大意：有一个全为0的数组a，有一个费用数组c，给出总的可用费用k，每次操作可以花费c[i]使a[1]~a[i]中所有数+1，要求使a的字典序最大，输出满足条件的a

1<=n<=2e5；1<=c[i]<=1e9

思路：因为要a的字典序最大，所以初始状态下我们要找一个ma=k/c[i]最大，且i最大的位置mai，1~mai中的所有数都应该等于ma，显然，在这个区间内选择其他任意方案字典序都不如这样大。

接下来考虑剩下来的mai+1~n的区间，我们可能在这里面选择一些数，替换掉之前的mai位置的数，即如果a[mai]*(ma-x)+x*a[i]<=k，那么我们就可将x个a[mai]换成x个a[i]，这样1~mai中的数不变，mai+1~i的数都等于x。移项化简得x=(k-ma*a[mai])/(a[i]-a[mai])，即x=(k%a[mai])/(a[i]-a[mai])，这样1~i都处理好了，k=k%a[mai]%a[i]，继续依照此法循环处理剩余的区间，每次区间+ma都用差分数组维护，直到k=0，后面的数肯定都是0了，退出循环。

那么这样做会不会超时呢？首先考虑我们最终构造出的a数组中最多有多少不同数字，因为这些事都是k%一个数得出来的，对一个数取模最坏的情况就是对这个数/2+1取模，也就是最多进行log2(1e9)次取模，a中的数也就不超过30个，我们每次得出这个数都是O(n)的时间复杂度，最终的时间复杂度就是O(log(a[i])*n)，在可接受范围内。

//#include<__msvc_all_public_headers.hpp>
#include
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
ll n;
ll a[N];
int l[N], r[N];
bool vis[N];
int k;
int sum[N];
void init()
{
	for (int i = 1; i <= n+1; i++)
	{//初始化差分数组
		sum[i] = 0;
	}
}
void solve()
{
	cin >> n;
	init();
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	cin >> k;
	int ma = 0, mai = 0;//当前区间k/c[i]的最大值，最大值下标
	int pre = 0;//上一个区间内的最大值
	int now = 1;//待处理的区间的左端点
	while(1)
	{
		for (int i = now; i <= n; i++)
		{//遍历整个数组，得到k/c[i]的最大值
			if (k / (a[i]-pre) >= ma)
			{
				ma = k / (a[i]-pre);
				mai = i;
			}
		}
		sum[now] += ma;//差分数组区间+
		sum[mai + 1] -= ma;
		if (!ma)//最大值为0后面就都是0了
			break;
		k%=a[mai] - pre;//维护新的k
		if (!k)//k变成0后面就都是0了
			break;
		now = mai + 1;//维护待处理的区间的左端点
		if (now > n)
			break;
		pre = a[mai];
		ma = 0;
	}
	for (int i = 1; i <= n; i++)
	{
		sum[i] = sum[i - 1] + sum[i];
		cout << sum[i] << " ";
	}
	cout << endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while (t--)
	{
		solve();
	}
	return 0;
}