题解：CF754D Fedor and coupons
__vector__
·
·
题解
假设答案的左端点是 x，那么右端点 y 怎么求？
明显的，在左端点小于等于 x 的区间里面选择 k 个右端点最大的，其中右端点第 k 大的区间的右端点就是 y。
即使这 k 个区间没有一个左端点等于 x 的也无所谓，这样只会让答案变大，但是按照这个方法枚举一遍所有可能的 x，最优解是一定会枚举到的。
为了快速实现这个程序，可以将升序枚举答案的左端点 x，每枚举一个新的 x 就将左端点为 x 的区间加入候选集合，然后候选集合删掉右端点最小的，直到大小不超过 k，可以用 set 维护这个集合。
```cpp
#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？
*/
```