[数据结构与算法]codeforce1671C. Dolce Vita

传送门：誰にだって訳があって、今を生きって

水题碰彩笔，我直接嘤嘤嘤
思路很简单，就是挑着便宜的买，因为所有商品每次涨价幅度一样，所以预算不超，买的方式和上一轮一样；如果超了，不要最贵的。
重点再于实现细节

#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define Pair pair<int,int>
#define re return

#define getLen(name,index) name[index].size()
#define mem(a,b) memset(a,b,sizeof(a))
#define Make(a,b) make_pair(a,b)
#define Push(num) push_back(num)
#define rep(index,star,finish) for(register int index=star;index<finish;index++)
#define drep(index,finish,star) for(register int index=finish;index>=star;index--)
using namespace std;

template<class T> void _deb(const char *name,T val){
    cout<<name<<val<<endl;
}
const int MAXN = 2e5+5;

int t;
ll store[MAXN];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>t;
    while(t--) {
        int n,x;
        cin>>n>>x;
        rep(i,0,n){
            cin>>store[i];
        }
        store[n] = 0;

        //sort
        sort(store, store+n);

        ll p0 = 0, base_cost = 0;
        // adapt for the loop logic 
        while( p0 < n ) {
            base_cost += store[p0];
            if(base_cost <= x)
                p0 ++;
            else
                break;
        }

		// not ini with 0
        ll ans = p0;
        ll last_day = 0;
        while(p0 > 0) {
            ll ini_cost = base_cost - store[p0];
            ll turn_cost = ini_cost + p0*last_day;
            ll now = (x-turn_cost) / p0;
//            cout<<"amount:"<<p0<<" and n is:"<<now<<endl;

            ans += now * p0;
            last_day += now;

            p0 --;
            base_cost = ini_cost;
        }

        cout<<ans<<endl;
    }

    re 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖