牛客网 桂林电子科技大学第三届ACM程序设计竞赛 C.二元-K个二元组最小值和最大-优先队列+贪心(思维)
链接：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≤105
,1≤ai
,bi
≤109
一开始以为是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;
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.a>>x.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.b);
28 }
29 ll y=q.top();
30 ll ans=x.a+y;
31 for(int i=k+1;i<=n;i++){
32 q.push(x.b);q.pop();
33 y=q.top();
34 if(ans<y+x.a) ans=y+x.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;
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.a>>x.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.b);
28 }
29 ll ans=-1;
30 for(int i=k;i<=n;i++){
31 q.push(x.b);
32 ll y=q.top();
33 ans=max(ans,y+x.a);
34 q.pop();
35 }
36 cout<<ans<<endl;
37 return 0;
38 }
文档来源：51CTO技术博客https://blog.51cto.com/u_15310764/3167969
页:
[1]