P6044 [POI2018] Prawnicy 题解

· · 题解

分析题意

简要题意

即有 n 条线段，选出 k 条线段，使得他们的交集长度最大并输出任意一种方案。

易知最终得到的区间是某一线段的左端点与另一线段的右端点。

解题思路

贪心

若先判断左端点，那将左端点按值从小到大排序，然后从前遍历即可。

优先队列

剩下只用判断右端点，需要维护 k 条线段的右端点值，那么用优先队列，可以比较方便的得出。针对该题，我们使用小根堆。

如何获得答案

维护合法右端点减去左端点的最大值，最后输出即可。

对于线段的编号，需要顺带维护最大长度的左端点与右端点，记为 l 和 r。我们重新遍历一边，找到左端点小于等于 l 和右端点大于等于 r 的线段，输出即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,k,tail,head,tim;
struct node{int x,y,num;}a[N];
priority_queue<int,vector<int >,greater<int > >r;//小根堆
bool cmp(node a,node b){
    return a.x==b.x?(a.y<b.y):(a.x<b.x);
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
        a[i].num=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        r.push(a[i].y);
        while(r.size() >k){
            r.pop();
        }
        if(r.size()==k){ //如果合法
            if(tim<(r.top()-a[i].x)){//替换
                tail=r.top();head=a[i].x;
                tim=tail-head;
            }
        }
    }
    cout<<tim<<endl;
    for(int i=1;i<=n;i++){//重新遍历
        if(a[i].x<=head&&a[i].y>=tail&&k){
            k--;
            cout<<a[i].num<<" ";
        }
    }
    return 0;
}