本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-18 16:32:19

假设答案的左端点是 $x$，那么右端点 $y$ 怎么求？

明显的，在左端点小于等于 $x$ 的区间里面选择 $k$ 个右端点最大的，其中右端点第 $k$ 大的区间的右端点就是 $y$。

即使这 $k$ 个区间没有一个左端点等于 $x$ 的也无所谓，这样只会让答案变大，但是按照这个方法枚举一遍所有可能的 $x$，最优解是一定会枚举到的。

为了快速实现这个程序，可以将升序枚举答案的左端点 $x$，每枚举一个新的 $x$ 就将左端点为 $x$ 的区间加入候选集合，然后候选集合删掉右端点最小的，直到大小不超过 $k$，可以用 set 维护这个集合。

$x$ 的数量也只有不超过 $n$ 个，因为任意一个合法的 $x$ 必然是某个区间的左端点。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x\/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
const int maxn=3e5+5;
int n,k;
struct PII{
    int fi,se,id;
}seq[maxn];
void solve(int id_of_test){
	read(n);
    read(k);
    FOR(i,1,n){
        read(seq[i].fi);
        read(seq[i].se);
        seq[i].id=i;
    }
    sort(seq+1,seq+n+1,[&](PII& a,PII& b){
        if(a.fi!=b.fi)return a.fi<b.fi;
        return a.se<b.se;
    });
    multiset<pii> s;
    int ans=0,ansid;
    FOR(i,1,n){
        if(s.size()>=k){
            s.erase(s.begin());
        }
        s.insert(mkpr(seq[i].se,seq[i].id));
        if(s.size()==k){
            int j=s.begin()->fi;
            if(j-seq[i].fi+1>ans){
                ans=j-seq[i].fi+1;
                ansid=i;
            }
        }
    }
    if(!ans){
        printf("%d\n",ans);
        FOR(i,1,k)printf("%d ",i);
        pln
        return;
    }
    s.clear();
    FOR(i,1,n){
        s.insert(mkpr(seq[i].se,seq[i].id));
        if(s.size()>k)s.erase(s.begin());
        if(i==ansid){
            printf("%d\n",ans);
            for(auto v:s)printf("%d ",v.se);
            pln
            return;
        }
    }
}
int main()
{
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}
\/*
1. 对题意的理解能否和样例对的上？  
2. 每一步操作，能否和自己的想法对应上？  
3. 每一步操作的正确性是否有保证？  
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？  
*\/