撰写2 seconds
256 megabytes
standard input
standard output
There are nn TV shows you want to watch. Suppose the whole time is split into equal parts called “minutes”. The ii-th of the shows is going from lili-th to riri-th minute, both ends inclusive.
You need a TV to watch a TV show and you can’t watch two TV shows which air at the same time on the same TV, so it is possible you will need multiple TVs in some minutes. For example, if segments [li,ri][li,ri] and [lj,rj][lj,rj] intersect, then shows ii and jj can’t be watched simultaneously on one TV.
Once you start watching a show on some TV it is not possible to “move” it to another TV (since it would be too distracting), or to watch another show on the same TV until this show ends.
There is a TV Rental shop near you. It rents a TV for xx rupees, and charges yy (y<xy<x) rupees for every extra minute you keep the TV. So in order to rent a TV for minutes [a;b][a;b] you will need to pay x+y⋅(b−a)x+y⋅(b−a).
You can assume, that taking and returning of the TV doesn’t take any time and doesn’t distract from watching other TV shows. Find the minimum possible cost to view all shows. Since this value could be too large, print it modulo 109+7109+7.
The first line contains integers nn, xx and yy (1≤n≤1051≤n≤105, 1≤y<x≤1091≤y<x≤109) — the number of TV shows, the cost to rent a TV for the first minute and the cost to rent a TV for every subsequent minute.
Each of the next nn lines contains two integers lili and riri (1≤li≤ri≤1091≤li≤ri≤109) denoting the start and the end minute of the ii-th TV show.
Print exactly one integer — the minimum cost to view all the shows taken modulo 109+7109+7.
5 4 3 1 2 4 10 2 4 10 11 5 9
60
6 3 2 8 20 6 22 4 15 20 28 17 25 20 27
142
2 1000000000 2 1 2 2 3
999999997
In the first example, the optimal strategy would be to rent 33 TVs to watch:
- Show [1,2][1,2] on the first TV,
- Show [4,10][4,10] on the second TV,
- Shows [2,4],[5,9],[10,11][2,4],[5,9],[10,11] on the third TV.
This way the cost for the first TV is 4+3⋅(2−1)=74+3⋅(2−1)=7, for the second is 4+3⋅(10−4)=224+3⋅(10−4)=22 and for the third is 4+3⋅(11−2)=314+3⋅(11−2)=31, which gives 6060 int total.
In the second example, it is optimal watch each show on a new TV.
In third example, it is optimal to watch both shows on a new TV. Note that the answer is to be printed modulo 109+7109+7.
题意：给n，x，y以及长度为n的l,r。x代表租金，y代表超出一小时后的每小时的租金，[l,r]代表该电视节目播放时间，所以一台租一台电视所需金钱要么为x+（r-l）*y要么为接着（上次使用的中间时长+本次时长）*y，求出最少租金。
题解：实际上，就是将x与最小（即最近）的空闲时间所需金钱比较，二取一即可（反证法可证）。将结构体按照l从小到大排序，将r输入multiset中，注意，s.earse(*it)会删除所有该元素，删除单个的操作为s.erase(s.find(*it))。
代码：
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
const int maxn = 1e5+5;
struct segment{
ll le;
ll ri;
}seg[maxn];
bool cmp(segment &a,segment &b){
return a.le<b.le;
}
multiset<ll>s;
int main(){
int n;
ll x,y,ans=0;
cin>>n>>x>>y;
rep(i,1,n){
cin>>seg[i].le>>seg[i].ri;
s.insert(seg[i].ri);
}
sort(seg+1,seg+n+1,cmp);
multiset<ll>::iterator it;
rep(i,1,n){
ll l=seg[i].le,r=seg[i].ri;
it=s.lower_bound(seg[i].le);
if(it==s.begin()) {
ans=(ans+x+y*(r-l)%mod)%mod;
}
else{
it--;
ll r0=*it;
if((l-r0)*y-x<=0){
ans=(ans+y*(r-r0)%mod)%mod;
s.erase(s.find(r0));
}else{
ans=(ans+x+y*(r-l)%mod)%mod;
}
}
}
cout<<ans<<endl;
}
/*
20 10 2
11 30
20 27
24 25
24 29
16 21
30 30
28 29
29 30
21 29
20 26
29 29
29 30
25 28
26 26
20 27
2 18
27 29
6 22
27 27
16 29
*/