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

你的名字 2024-03-17 16:07 77阅读 0赞

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

题意：

![be335365e2894b9c8fd148f05f07bb9c.png][]

思路：

经典中的经典中的经典

还是一样双指针把可行解放入DS中，然后求最优解

值得注意的是，我们说的双指针的单调性，指的是 j 指针前面所有元素都能满足 ai 以及 ai 以后这个条件

Code：

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

[Wannafly_15_ACM_NOI_CSP_CCPC_ICPC_OJ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/112#question
[be335365e2894b9c8fd148f05f07bb9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/1263a34218804e0b9f72d3bd069c71d6.png

发表评论取消回复

表情：

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

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

相关阅读

相关【裴属定理】Wannafly挑战赛22 A

[A-计数器\_Wannafly挑战赛22 (nowcoder.com)][A-_Wannafly_22 _nowcoder.com] 题意： ![4302eb25c979

「爱情、让人受尽委屈。」/ 2024年03月17日 16:07/ 0 赞/ 82 阅读

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

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

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

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

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

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

相关 Wannafly 挑战赛5

A 题: 星神是来自宇宙的所以珂朵莉也是吧所以我就出了个题给你一个长为n的序列a，有n\(n+1)/2个子区间，问这些子区间里面和为完全平方数的子区间个数 in

柔情只为你懂/ 2022年06月03日 01:58/ 0 赞/ 321 阅读

相关 Wannafly挑战赛5 A.珂朵莉与宇宙

Wannafly挑战赛5 A.珂朵莉与宇宙题目描述星神是来自宇宙的所以珂朵莉也是吧所以我就出了个题

一时失言乱红尘/ 2022年06月02日 02:16/ 0 赞/ 205 阅读

相关 Wannafly挑战赛9

A 题目描述给定n个正整数，请找出其中有多少个数x满足：在这n个数中存在数y=kx，其中k为大于1的整数输入描述: 第一行输入一个n

朱雀/ 2022年05月31日 01:54/ 0 赞/ 213 阅读

相关 Wannafly挑战赛11 -A 白兔的分身术

链接： [https://www.nowcoder.com/acm/contest/73/A][https_www.nowcoder.com_acm_contest_73_A]

ゞ浴缸里的玫瑰/ 2022年05月30日 12:37/ 0 赞/ 205 阅读

相关 Wannafly挑战赛23 A ：字符串（尺取法）

[题目传送门][Link 1] 代码： include<bits/stdc++.h> using namespace std; cons

╰半夏微凉°/ 2022年05月14日 06:28/ 0 赞/ 185 阅读

相关 Wannafly挑战赛25 A 因子数学

[题面][Link 1] 题意:令 X = n!,给定一大于1的正整数p,求一个k使得 p ^k | X 并且 p ^(k + 1) 不是X的因子,n,,p(1e18>=n>

- 日理万妓/ 2021年12月21日 15:37/ 0 赞/ 212 阅读

相关牛客 Wannafly挑战赛24 A石子游戏(思维)

[题目链接][Link 1] 链接：[https://www.nowcoder.com/acm/contest/186/A][Link 1] 来源：牛客网 Alice

谁借莪１个温暖的怀抱￠/ 2021年09月16日 09:00/ 0 赞/ 338 阅读