BZOJ5102:[POI2018]Prawnicy(贪心,堆)

Description

定义一个区间(l,r)的长度为r-l，空区间的长度为0。

给定数轴上n个区间，请选择其中恰好k个区间，使得交集的长度最大。

Input

第一行包含两个正整数n,k(1<=k<=n<=1000000)，表示区间的数量。

接下来n行，每行两个正整数l,r(1<=l<r<=10^9)，依次表示每个区间。

Output

第一行输出一个整数，即最大长度。

第二行输出k个正整数，依次表示选择的是输入文件中的第几个区间。

若有多组最优解，输出任意一组。

Sample Input

6 3
3 8
4 12
2 6
1 10
5 9
11 12

Sample Output

4
1 2 4

Solution

把线段按左端点排序，从左到右扫一遍。

考虑以当前区间的左端点为答案的左端点，右端点肯定是已经扫过的前$k$大的右端点的最小值。

开个堆随便维护一下。

Code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<queue>
 5 #include<algorithm>
 6 #define N (1000009)
 7 using namespace std;
 8 
 9 struct Node{int l,r,id;}a[N];
10 int n,k,l,r,ans,x,y;
11 priority_queue<int,vector<int>,greater<int> >q;
12 
13 inline int read()
14 {
15     int x=0,w=1; char c=getchar();
16     while (c<'0' || c>'9') {if (c=='-') w=-1; c=getchar();}
17     while (c>='0' && c<='9') x=x*10+c-'0', c=getchar();
18     return x*w;
19 }
20 
21 bool cmp(Node a,Node b)
22 {
23     return a.l<b.l;
24 }
25 
26 int main()
27 {
28     n=read(); k=read();
29     for (int i=1; i<=n; ++i)
30     {
31         l=read(); r=read();
32         a[i]=(Node){l,r,i};
33     }
34     sort(a+1,a+n+1,cmp);
35     for (int i=1; i<=n; ++i)
36     {
37         q.push(a[i].r);
38         if (q.size()>k) q.pop();
39         if (q.size()==k && q.top()-a[i].l>ans)
40             ans=q.top()-a[i].l, x=a[i].l, y=q.top();
41     }
42     printf("%d
",ans);
43     for (int i=1; i<=n; ++i)
44         if (a[i].l<=x && a[i].r>=y)
45         {
46             printf("%d ",a[i].id);
47             k--;
48             if (!k) break;
49         }
50 
51 }