CodeForces 754D Fedor and coupons

本文主要是介绍CodeForces 754D Fedor and coupons，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：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;
}

这篇关于CodeForces 754D Fedor and coupons的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---