题目大意：有一个全为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<bits/stdc++.h>
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;
}