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

绝地灬酷狼 2024-03-17 15:40 41阅读 0赞

[D - Shipping Center (atcoder.jp)][D - Shipping Center _atcoder.jp]

题意：

![86fab8a4ccff401ab149206f94a047f0.png][]

思路：

经典中的经典，二维属性，对于其中的一个关键字排序，然后双指针将合法的可行解放入容器中，再去容器中找最优解，用双指针是因为它具有单调性

这里的最优解就是找出体积第一个>=它的，然后匹配

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e3+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    struct ty{
    	int w,v;
    }a[mxn];
    
    int N,M,Q,l,r;
    int x[mxn];
    
    bool cmp(ty x,ty y){
    	if(x.v==y.v) return x.w>y.w;
    	return x.v>y.v;
    }
    void solve(){
    	cin>>N>>M>>Q;
    	for(int i=1;i<=N;i++) cin>>a[i].w>>a[i].v;
    	for(int i=1;i<=M;i++) cin>>x[i];
    	sort(a+1,a+1+N,cmp);
    	while(Q--){
    		cin>>l>>r;
    		multiset<int> S;
    		for(int i=1;i<=M;i++){
    			if(i<l||i>r) S.insert(x[i]);
    		}
    		int ans=0;
    		for(int i=1;i<=N;i++){
    			auto it=S.lower_bound(a[i].w);
    			if(it!=S.end()){
    				ans+=a[i].v;
    				S.erase(it);
    			}
    		}
    		cout<<ans<<'\n';
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[D - Shipping Center _atcoder.jp]: https://atcoder.jp/contests/abc195/tasks/abc195_d
[86fab8a4ccff401ab149206f94a047f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c7b23e8b4d74467d93d1687438f5f2e6.png

发表评论取消回复

表情：

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

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

相关阅读

相关【二分/双指针】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 赞/ 34 阅读

相关【多维BFS】ABC311 D

[D - Grid Ice Floor][] 题意： ![21929a903e384fb5ba0355f5a95a8438.png][] 思路：可以发现，这种魔改BF

Dear 丶/ 2024年03月22日 19:58/ 0 赞/ 72 阅读

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

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

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

相关【二维属性+贪心+双指针】Wannafly 挑战赛15 A

[Wannafly挑战赛15\_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛\_牛客竞赛OJ (nowcoder.com)][Wannafly_15_ACM_

你的名字/ 2024年03月17日 16:07/ 0 赞/ 66 阅读

相关 ABC 195 C

不知道该怎么解释这道题，反正我不太会，感觉很帅题意： ![5ea04594676f4a78a31bec299de61d1a.png][] Code： incl

た入场券/ 2024年03月17日 15:40/ 0 赞/ 42 阅读

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

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

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

相关【DP+博弈】ABC195 E

[E - Lucky 7 Battle (atcoder.jp)][E - Lucky 7 Battle _atcoder.jp] 题意： ![44faf1c04ab542

ゞ浴缸里的玫瑰/ 2024年03月17日 15:40/ 0 赞/ 38 阅读

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

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

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

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

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

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

相关【多维BFS】ABC308 D

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

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