codeforces round390 div2 C Fedor and coupons

/* 题目描述：给出n(0 < n < 1e5)条线段，问用其中k条线段能覆盖住的最大长度是多少？ 思路：首先对线段的所有端点进行离散化，将所有线段按照左端点小的在前，左端点相同在后的原则进行排序，再建立一个 优先队列，令其越靠近队头的线段的右端点越小。 从离散化后的第一个端点开始，向后依次枚举，对于每一个端点（假设其离散化之前为l），在排序后的线段的数组中， 将左端点在这个端点以左所有线段入队，然后不断出队直至队中元素正好为k个(若本身不满k个就枚举下一个端点)，取出 队头元素，假设其右端点为r，那么ans = max(ans , r - l + 1)，最终ans即为答案 收获：对于线段的这类问题，先将线段排序，在搞优先队列可以看作为一种套路，曾出现在hdu5862 */ #pragma warning(disable:4786) #pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<vector> #include<cmath> #include<string> #include<sstream> #include<bitset> #define LL long long #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i) #define mem(a,x) memset(a,x,sizeof(a)) #define lson l,m,x<<1 #define rson m+1,r,x<<1|1 using namespace std; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const double PI = acos(-1.0); const double eps=1e-6; const int maxn = 3e5 + 5; vector<int>output; struct node { int l , r , id; bool operator < (const node & rhs)const{ return r > rhs.r; } }seg[maxn]; bool cmp(const node a , const node b) { if(a.l < b.l) return true; else if(a.l == b.l) return a.r < b.r; else return false; } priority_queue<node>Q; vector<int>v; map< int , int >mp; int bsearch(int left , int right , int val) { int ret = -1 , mid; while(left <= right){ mid = left + (right - left) / 2; if(seg[mid].l <= val){ ret = mid; left = mid + 1; } else{ right = mid - 1; } } return ret; } int main() { int n , k; scanf("%d %d", &n , &k); for(int i = 1 ; i<= n ; i++){ scanf("%d %d", &seg[i].l , &seg[i].r); seg[i].id = i; v.push_back(seg[i].l); v.push_back(seg[i].r); } sort(v.begin() , v.end() ); int cnt = unique(v.begin() , v.end()) - v.begin(); sort(seg + 1 , seg + n + 1 , cmp); for(int i = 0 ; i< cnt ; i++){ mp[v[i]] = i + 1 ; } for(int i = 1 ; i<= n; i++){ seg[i].l = mp[seg[i].l]; seg[i].r = mp[seg[i].r]; } int i , j = 1 , ans = 0 , ansl , ansr , right; for(i = 1 ; i<= cnt ; i++){ right = bsearch(1 , n , i); for(; j <= right ; j++){ Q.push(seg[j]); } int siz = Q.size(); if(siz < k) continue; while(Q.size() > k) Q.pop(); int cur = Q.top().r; if(cur < i) continue; if(v[cur - 1] - v[i - 1] + 1 > ans){ ans = v[cur - 1] - v[i - 1] + 1 ; ansl = i; ansr = cur; } } if(!ans){ printf("%d\n", ans); for(int i = 1 ; i<= k ; i++){ if(i != k) printf("%d ", i); else printf("%d\n", k); } } else{ for(int i = 1 ; i<= n ; i++){ if(seg[i].l <= ansl && seg[i].r >= ansr) output.push_back(seg[i].id); if(output.size() == k) break; } printf("%d\n",ans); for(int i = 0 ; i < output.size() ; i++){ if(i != output.size() -1 ) printf("%d ",output[i]); else printf("%d\n", output[i]); } } return 0; }