首页 > 其他分享 >Codeforces Round 946 (Div. 3) G Money Buys Less Happiness Now(反悔贪心)

Codeforces Round 946 (Div. 3) G Money Buys Less Happiness Now(反悔贪心)

时间:2024-05-23 20:19:30浏览次数:27  
标签:Now Less 946 Money Buys now Happiness

Money Buys Less Happiness Now

1.题目大意:
有n天,每天可以赚x块钱,然后每天可以通过花\(C_{i}\)块钱购买1点快乐值,然后每天赚的钱至少要在下一天才能用,问最多能获得多少快乐值。
2.解题思路:
我们发现天数变得很多,不能像e题那样dp了,所以要用贪心。具体来讲,我们碰到当前能买的就直接买,如果买不了,就从之前买过的但是比自己贵的那些物品里面挑一个最贵的,然后用当前的物品替换。可以发现这样一定是最优的,因为换掉最贵的就一定能留下更多的钱买后面的物品。(可能从来没做过这样的题吧,所以想半天一点思路都没有
3.代码:

void solve() {
    ll n, x;cin >> n >> x;
    vi a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    ll now = 0;
    priority_queue<ll> q;
    for(int i = 1; i <= n; i++) {
        if(now >= a[i]) {
            now -= a[i];
            q.push(a[i]);
        } else {
            if(!q.empty() && q.top() > a[i]) {
                now += q.top() - a[i];
                q.pop();
                q.push(a[i]);
            }
        }
        now += x;
    }
    cout << q.size() << "\n";
}

标签:Now,Less,946,Money,Buys,now,Happiness
From: https://www.cnblogs.com/orzkeyhacker/p/18209242

相关文章

  • Codeforces Round 946 (Div. 3)
    C.BeautifulTriplePairs题意:优美组的定义是一共三对有且只有一对对应的数字不相同,求有多少个优美三元组思路:对于只有三对,而且只有一对不同,首先看前面遍历过的三元组会对后面的三元组产生影响,若是不记录前面对后面三元组的次数,那么我们要进行两次循环O(n^2)会寄的,因此我们......
  • 上海站丨飞天技术沙龙 Serverless + AI 专场开启报名!
    活动简介“飞天技术沙龙——Serverless技术实践营”是一场以Serverless为主题的技术活动,通过一个下午的时间增进对Serverless技术的理解,快速上手,活动受众以关注Serverless技术的开发者、企业决策人、云原生领域创业者为主,活动形式为演讲、动手实操。Serverless和AI大......
  • 新概念第三册 lession1
    Wheremustthepumahavecomefrom?Pumasarelarge,cat-likeanimalswhicharefoundinAmerica.WhenreportscameintoLondonZoothatawildpumahadbeenspottedforty-fivemilessouthofLondon,theywerenottakenseriously.However,astheeviden......
  • E. Money Buys Happiness
    原题链接题解观察到h不大于1e5,于是拿h做文章如果想要在第\(i\)个月的幸福值达到\(j\)那么第\(i-1\)个月的幸福值一定能达到\(j-h_i\)而且\(cost_{[i-1][j-h_i]}+c_i\leqx·(i-1)\)记得用滚动数组优化,因为这里\(i\)只和\(i-1\)的小幸福值有关code#include<bit......
  • G. Money Buys Less Happiness Now
    原题链接题解假如最后有\(k\)个月购买过幸福,那么这\(k\)个月的价格一定是前\(k\)小的code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);intt;cin>>t;whil......
  • lesson11
    单词guiltyadj有罪的,内疚的beguiltyof...Heisguiltyofmurderbeinnocentof...innocencenhaveaclearconscience问心无愧guiltn有罪的crimen犯罪commitaseriouscrimesinn宗教上道德的罪itisasintotellaliedeclarev(向税务部门)申报,宣布......
  • lesson10
    单词colossaladj庞大的huge/great/immense/enormous/gigantic/titanictragicadj悲剧的,悲惨的comic喜剧的dramanic戏剧的linern班轮airlinern班机yachtn游艇ferry渡轮raft木筏dinghy橡皮艇canoe独木舟kayak激流运动的独木舟voyagen航行beonav......
  • lesson9
    单词fascinatev迷住iamfascinatedbythestorybe/find...endlesslyfascinatingfascinationn魅力haveafascinationfor...对....有特别的魅力affectionateaffectionn爱maternal/paternalaffection母爱/父爱mysteriousadj神秘的mysteryn谜beamyste......
  • 上海站丨飞天技术沙龙 Serverless + AI 专场开启报名!
    活动简介“飞天技术沙龙——Serverless技术实践营”是一场以Serverless为主题的技术活动,通过一个下午的时间增进对Serverless技术的理解,快速上手,活动受众以关注Serverless技术的开发者、企业决策人、云原生领域创业者为主,活动形式为演讲、动手实操。Serverless和A......
  • CF Round946 (Div. 3)B:如何写映射
    SymmetricEncoding题目描述Polycarphasastring$s$,whichconsistsoflowercaseLatinletters.Heencodesthisstringusingthefollowingalgorithm:first,heconstructsanewauxiliarystring$r$,whichconsistsofalldistinctlettersofthestrin......