题目链接：http://codeforces.com/contest/754/problem/D 题意：给你n个优惠券，每个优惠券是一个区间，他能给这个区间的所有商品进行打折，现让你选择k个优惠券，使得能够重复打折的商品最大，让你输出有多少个商品被打折了，并输出你选择的优惠券编号 解析！：其实说白了就是给你n个区间，每个区间会覆盖一个范围，让你选择k个区间，使得你重复覆盖的范围尽可能大，那么我们可以按照左区间排序从小到大排序，然后去维护一个大小为k的优先队列，按右区间小的现出来，答案就是此时的右区间减左区间
#include <bits/stdc++.h> using namespace std; const int maxn = 3e5+100; struct node { int l,r; int id; node() {} node(int _l,int _r,int _id) { l = _l; r = _r; id = _id; } bool operator < (const node &b)const { return l<b.l; } }a[maxn]; int main(void) { int n,k; scanf("%d %d",&n,&k); for(int i=0;i<n;i++) { scanf("%d %d",&a[i].l,&a[i].r); a[i].id = i+1; } sort(a,a+n); int ans = 0,l,r; priority_queue<int,vector<int>,greater<int> >q; for(int i=0;i<n;i++) { q.push(a[i].r); if(q.size()>k) q.pop(); int sum = q.top()-a[i].l+1; if(ans<sum && q.size()==k) { ans = sum; l = a[i].l; r = a[i].l+sum-1; } } printf("%d\n",ans); if(ans==0) { for(int i=1;i<=k;i++) printf("%d ",i); puts(""); } else { for(int i=0;i<n;i++) { if(a[i].l<=l && a[i].r >=r) { printf("%d ",a[i].id); k--; } if(k==0) break; } puts(""); } return 0; }