【贪心+双指针】ABC308 F

r囧r小猫 2024-03-17 13:55 81阅读 0赞

[F - Vouchers (atcoder.jp)][F - Vouchers _atcoder.jp]

题意：

![b9d9dfba42284ccb967e5089f644eec9.png][]

思路：

做法就是贪心

贪心结论就是，每次选合法的券中优惠最大的

合法指本身的价格够上L值

因此我们可以把物品和券都排序

对于每个物品，我们把合法的券扔进优先队列中，找到d最大的即可

注意到可以选的券具有单调性，可以用双指针维护

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int Inf=0x3f3f3f3f;
    
    struct ty{
        int d,l;
    }a[mxn];
    
    priority_queue<int> Q;
    
    int N,M;
    int p[mxn],d[mxn],l[mxn];
    
    bool cmp(ty x,ty y){
        if(x.l==y.l) return x.d<y.d;
        return x.l<y.l;
    }
    void solve(){
        cin>>N>>M;
        for(int i=1;i<=N;i++) cin>>p[i];
        for(int i=1;i<=M;i++) cin>>a[i].l;
        for(int i=1;i<=M;i++) cin>>a[i].d;
        sort(p+1,p+1+N);
        sort(a+1,a+1+M,cmp);
        int j=1;
        int ans=0;
        for(int i=1;i<=N;i++){
            while(j<=M&&a[j].l<=p[i]) Q.push(a[j].d),j++;
            if(Q.size()){
                ans+=p[i]-Q.top();
                Q.pop();
            }else{
                ans+=p[i];
            }
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[F - Vouchers _atcoder.jp]: https://atcoder.jp/contests/abc308/tasks/abc308_f
[b9d9dfba42284ccb967e5089f644eec9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/07650ffdcec24ba19c26c979a7cb2471.png

发表评论取消回复

表情：

评论列表（有 0 条评论，81人围观）

还没有评论，来说两句吧...

相关阅读

相关 ABC278 F - Shiritori

不懂博弈和状压DP，今晚加训状压DP！博弈太难了，东西太多了，等蓝桥杯打完再说QwQ [F - Shiritori (atcoder.jp)][F - Shiritori

向右看齐/ 2024年03月25日 23:29/ 0 赞/ 69 阅读

相关【二分/双指针】ABC250 D - 250-like Number

[D - 250-like Number (atcoder.jp)][D - 250-like Number _atcoder.jp] 题意： ![9ef9c6e12b16

深碍√TFBOYSˉ_/ 2024年03月23日 11:35/ 0 赞/ 49 阅读

相关【双指针】ABC229 D - Longest X

感觉这道题很简单啊，应该想彻底了再看题解的.... [D - Longest X (atcoder.jp)][D - Longest X _atcoder.jp] 题意：

蔚落/ 2024年03月22日 11:02/ 0 赞/ 49 阅读

相关【分段DP】ABC275 F

一万年没写DP了这么简单的DP我居然没写出来 [F - Erase Subarrays (atcoder.jp)][F - Erase Subarrays _atcode

叁歲伎倆/ 2024年03月22日 09:11/ 0 赞/ 59 阅读

相关【二维属性+贪心+双指针】ABC 195 D

[D - Shipping Center (atcoder.jp)][D - Shipping Center _atcoder.jp] 题意： ![86fab8a4ccff

绝地灬酷狼/ 2024年03月17日 15:40/ 0 赞/ 69 阅读

相关【二维偏序+双指针】ABC245 E

[E - Wrapping Chocolate (atcoder.jp)][E - Wrapping Chocolate _atcoder.jp] 题意： ![761342

女爷i/ 2024年03月17日 14:41/ 0 赞/ 95 阅读

相关【子序列+状压DP】ABC308 E MEX

这应该算是很套路的题，照理说是要做出来的 [E - MEX (atcoder.jp)][E - MEX _atcoder.jp] 题意： ![e6a5990b05cf48

雨点打透心脏的1/2处/ 2024年03月17日 13:55/ 0 赞/ 61 阅读

相关【贪心+双指针】ABC308 F

[F - Vouchers (atcoder.jp)][F - Vouchers _atcoder.jp] 题意： ![b9d9dfba42284ccb967e5089f6

r囧r小猫/ 2024年03月17日 13:55/ 0 赞/ 82 阅读

相关【多维BFS】ABC308 D

VP的时候居然花了半小时！可恶！ [D - Snuke Maze (atcoder.jp)][D - Snuke Maze _atcoder.jp] 题意： ![79

拼搏现实的明天。/ 2024年03月17日 13:55/ 0 赞/ 64 阅读

相关【贪心+双指针】阿宁睡大觉

[E-阿宁睡大觉\_牛客小白月赛56 (nowcoder.com)][E-_56 _nowcoder.com] 题意： ![3ce50b7a2e2140bb91ede8d3

た入场券/ 2024年03月16日 19:49/ 0 赞/ 49 阅读