[CF754D] Fedor and coupons - 贪心,堆
Description
给出n个区间,要求选出k个区间,是k个区间的并尽可能大
Solution
按 l 排序后顺序扫描,用一个堆维护 l 不超过当前的,最大的 k 个 r
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, k;
struct Node
{
int l, r, id;
bool operator<(const Node &rhs)
{
return l < rhs.l;
}
} a[N];
signed main()
{
ios::sync_with_stdio(false);
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i].l >> a[i].r;
a[i].id = i;
}
sort(a + 1, a + n + 1);
int ans = 0, ansx = 0;
priority_queue<int, vector<int>, greater<int>> que;
for (int i = 1; i <= n; i++)
{
que.push(a[i].r);
while (que.size() > k)
que.pop();
if (que.size() == k)
{
if (que.top() - a[i].l + 1 > ans)
{
ans = que.top() - a[i].l + 1;
ansx = a[i].l;
}
}
}
int left = ansx, right = ansx + ans - 1;
if (right < left)
right = -2e9, left = 2e9;
vector<int> res;
for (int i = 1; i <= n; i++)
if (a[i].l <= left && a[i].r >= right)
res.push_back(a[i].id);
cout << ans << endl;
for (int i = 0; i < k; i++)
cout << res[i] << " ";
cout << endl;
}