评论

收藏

[C++] 牛客网 桂林电子科技大学第三届ACM程序设计竞赛 C.二元-K个二元组最小值和最大-优先队列+贪心(思维)

编程语言 编程语言 发布于:2021-07-22 23:27 | 阅读数:513 | 评论:0

链接:https://ac.nowcoder.com/acm/contest/558/C
来源:牛客网


小猫在研究二元组。
小猫在研究最大值。
给定N个二元组(a1,b1),(a2,b2),…,(aN,bN),请你从中选出恰好K个,使得ai的最小值与bi的最小值之和最大。
请输出ai的最小值与bi的最小值之和

输入描述:
第一行两个正整数N,K,表示二元组数量与需要选的数量。接下来N行,第i行两个正整数ai,bi。
输出描述:
一行一个正整数,表示最大的a_i的最小值与b_i的最小值之和。
示例1

输入
复制
3 2
1 1
2 3
3 1
输出
复制3备注:
1≤N≤10
5
,1≤a
i,bi
≤10
9
一开始以为是dp,最后发现是贪心。
按照x从大到小排序,然后优先队列维护对应的y,维护y的最小值。
因为x是排好序的,所以相当于降了一维。
先删再进 和先进再删都是可以的。虽然删除的可能是x和y都最小的,但是x并没有出去,但是不影响,因为要的是最大值,所以不会对结果造成影响。
代码1(先进再删):
1 //C
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn=1e5+10;
 6  
 7 struct node{
 8   ll a,b;
 9  
10   friend bool operator<(node a,node b){
11     return a.a>b.a;
12   }
13  
14 }x[maxn];
15  
16  
17 int main()
18 {
19   ll n,k;
20   cin>>n>>k;
21   for(int i=1;i<=n;i++){
22     cin>>x[i].a>>x[i].b;
23   }
24   sort(x+1,x+1+n);
25   priority_queue<ll,vector<ll>,greater<ll> > q;
26   for(int i=1;i<=k;i++){
27     q.push(x[i].b);
28   }
29   ll y=q.top();
30   ll ans=x[k].a+y;
31   for(int i=k+1;i<=n;i++){
32     q.push(x[i].b);q.pop();
33     y=q.top();
34     if(ans<y+x[i].a) ans=y+x[i].a;
35   }
36   cout<<ans<<endl;
37   return 0;
38 }
代码2(先删再进):
1 //C
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn=1e5+10;
 6  
 7 struct node{
 8   ll a,b;
 9  
10   friend bool operator<(node a,node b){
11     return a.a>b.a;
12   }
13  
14 }x[maxn];
15  
16  
17 int main()
18 {
19   ll n,k;
20   cin>>n>>k;
21   for(int i=1;i<=n;i++){
22     cin>>x[i].a>>x[i].b;
23   }
24   sort(x+1,x+1+n);
25   priority_queue<ll,vector<ll>,greater<ll> > q;
26   for(int i=1;i<k;i++){
27     q.push(x[i].b);
28   }
29   ll ans=-1;
30   for(int i=k;i<=n;i++){
31     q.push(x[i].b);
32     ll y=q.top();
33     ans=max(ans,y+x[i].a);
34     q.pop();
35   }
36   cout<<ans<<endl;
37   return 0;
38 }

关注下面的标签,发现更多相似文章