小猫在研究二元组。
小猫在研究最大值。
给定N个二元组(a1,b1),(a2,b2),…,(aN,bN),请你从中选出恰好K个,使得ai的最小值与bi的最小值之和最大。
请输出ai的最小值与bi的最小值之和
题意:从这n个二元组中选择k个,使得ai的最小值与bi的最小值之和最大。
思路:将ai按从大小进行排序,由于ai已经排序好。如何从1-n进行遍历,将bi插入优先队列中(小根队)。
每次判断优先队列的大小是否等于k,保存此时的最大ans即可
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
struct node {
int x, y;
}a[maxn];
bool cmp(node a, node b) {
return a.x > b.x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
}
sort (a + 1, a + n + 1, cmp);
priority_queue<int, vector<int>,greater<int> > p;
int ans = 0;
for (int i = 1; i <= n; i++) {
p.push(a[i].y);
if (p.size() > k) {
p.pop();
}
if (p.size() == k) {
ans = max(ans, a[i].x + p.top());
}
}
cout << ans << endl;
return 0;
}