JZOJ5861. 【NOIP2018提高组模拟9.9】失意

题解

像这种求区间交集的问题，肯定是要对区间进行排序的。
按照r降序枚举，那么当前枚举到的r就一定是最小的右端点。
现在就要最小化l，但是要保证有m个l，
可以用堆来维护。
最后注意记录方案，直接记录答案交集区间是什么，
然后就直接输出包含这个交集区间的任意m个区间就好了。

code

#pragma GCC optimize(2) 
#pragma G++ optimize(2) 
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <time.h>
#define ll long long
#define N 1000003
#define M 103
#define db double
#define P putchar
#define G getchar
#define inf 998244353
#define pi 3.1415926535897932384626433832795
using namespace std;
char ch;
void read(int &n)
{
    n=0;
    ch=G();
    while((ch<'0' || ch>'9') && ch!='-')ch=G();
    ll w=1;
    if(ch=='-')w=-1,ch=G();
    while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G();
    n*=w;
}

struct node
{
    int l,r,id;
}a[N];

struct arr
{
    int l,id;
}ttt;

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
ll abs(ll x){return x<0?-x:x;}
ll sqr(ll x){return x*x;}
void write(ll x){if(x>9) write(x/10);P(x%10+'0');}

priority_queue <arr> q,w;
bool operator <(arr a,arr b)
{
    return a.l<b.l;
}
int n,m,ans,t,ansl,ansr;

bool cmp(node a,node b){return a.r>b.r;}

int main()
{
    freopen("failure.in","r",stdin);
    freopen("failure.out","w",stdout);

    read(n);read(n);read(m);
    for(int i=1;i<=n;i++)
        read(a[i].l),read(a[i].r),a[i].id=i;
    sort(a+1,a+1+n,cmp);

    for(int i=1;i<=m;i++)
        ttt.l=a[i].l,ttt.id=a[i].id,q.push(ttt);
    ans=a[m].r-q.top().l;ansl=q.top().l;ansr=a[m].r;

    for(int i=m+1;i<=n && a[i].r>ans;i++)
    {
        q.pop();
        ttt.l=a[i].l,ttt.id=a[i].id,q.push(ttt);
        t=a[i].r-q.top().l;
        if(t>ans)ans=t,ansl=q.top().l,ansr=a[i].r;
    }

    if(ans<0)ans=0;
    write(ans);P('\n');
    for(int i=1;i<=n && m;i++)
        if(a[i].l<=ansl && ansr<=a[i].r)write(a[i].id),P(' '),m--;

    return 0;
}