D-JZTXT

思路：

贪心找到尽可能靠右的最小值、次小值、次次小值，构成一个上升子序列，在该子序列上贪心操作。

记当前可用的钱为k，上一个位置为last_id，上一个位置的元素为last。当k全部用在上一个位置，会剩下k%last。

记当前的元素为cur，现在要使上一个位置用的个数保持不变，即考虑是否存在\(x\in[1,k/last]\)，满足\(\lfloor (x\cdot last+k\%last)/cur\rfloor=x\),我们贪心取\(x=min((k\%last)/(cur-last),k/last)\),即看当前的k%last可以分担给多少(cur-last)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
bool cmp(P x,P y)
{
    if(x.first==y.first)
    {
        return x.second>y.second;
    }else
    {
        return x.first<y.first;
    }
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        vector<int>a(n+2);
        vector<P>v;
        for(int i=1;i<=n;i++)
        {
            int x;cin>>x;
            a[i]=x;
            v.push_back({x,i});
        }
        int k;cin>>k;
        sort(v.begin(),v.end(),cmp);
        
        vector<int>res(n+2);
        int last_id=v[0].second;
        int last=v[0].first;
        res[v[0].second]=k/a[v[0].second];

        for(int i=1;i<v.size();i++)
        {
            if(v[i].first==last)
            {
                continue;
            }else if(v[i].second<last_id)
            {
                continue;
            }else
            {
                k=min((k%last)/(v[i].first-last),k/last)*last+k%last;
                res[v[i].second]=k/v[i].first;
                last=v[i].first;
                last_id=v[i].second;
            }
        }

        for(int i=n;i>=1;i--)
        {
            if(res[i]==0)
            {
                res[i]=res[i+1];
            }
        }

        for(int i=1;i<=n;i++)
        {
            cout<<res[i]<<" ";
        }
        cout<<endl;
        
    }
}