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

 #include<iostream>
 #include<cstring>
 #include<cstdio>
 #include<queue>
 #include<algorithm>
 #define N (1000009)
 using namespace std; struct Node{int l,r,id;}a[N];
 int n,k,l,r,ans,x,y;
 priority_queue<int,vector<int>,greater<int> >q; inline int read()
 {
     int x=,w=; char c=getchar();
     while (c<'' || c>'') {if (c=='-') w=-; c=getchar();}
     while (c>='' && c<='') x=x*+c-'', c=getchar();
     return x*w;
 } bool cmp(Node a,Node b)
 {
     return a.l<b.l;
 } int main()
 {
     n=read(); k=read();
     for (int i=; i<=n; ++i)
     {
         l=read(); r=read();
         a[i]=(Node){l,r,i};
     }
     sort(a+,a+n+,cmp);
     for (int i=; i<=n; ++i)
     {
         q.push(a[i].r);
         if (q.size()>k) q.pop();
         if (q.size()==k && q.top()-a[i].l>ans)
             ans=q.top()-a[i].l, x=a[i].l, y=q.top();
     }
     printf("%d\n",ans);
     for (int i=; i<=n; ++i)
         if (a[i].l<=x && a[i].r>=y)
         {
             printf("%d ",a[i].id);
             k--;
             if (!k) break;
         } }