Codeforces Round #523 (Div. 2) D. TV Shows 模拟(多重集 先把所有区间加入多重集合)+贪心+二分

题意:给出n个电视节目的起始和结束时间  并且租一台电视需要x +y*(b-a)  【a,b】为时段

问完整看完电视节目的最小花费是多少

思路:贪心的思想 情况1 如果新租一台电视的花费<=在空闲电视上面看节目 那么肯定新租电视

        情况2 否则就直接在空闲电视上看 就好

模拟难(QAQ): 这里使用多重集合模拟   先把所有时间的pair(结束时间,开始时间) 放入多重集里面

然后开一个数组以l 从小到大排序

从数组小到大 枚举  在多重集里面找离终点最近的那个点 如果符合情况1 那么就删去 找到的那个点即可(因为 刚开始多重集有所有的区间 所以不用添加)

      否则情况2 直接加上值即可

 #include<bits/stdc++.h>
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
#define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr))
#define F first
#define S second
#define pii pair<int ,int >
#define mkp make_pair
#define pb push_back
#define arr(zzz) array<ll,zzz>
#define ll long long
using namespace std;
const int maxn=1e6+;
const int inf=0x3f3f3f3f;
const int mod=1e9+;
vector<pii>v;
multiset<pii>s;
int main(){
int n,x,y;
scanf("%d%d%d",&n,&x,&y);
int a,b;
for(int i=;i<=n;i++)scanf("%d%d",&a,&b),v.pb({a,b}),s.insert({b,a});
sort(v.begin(),v.end(),[](pii a,pii b){return a.F<b.F;});
ll ans=;
for(int i=;i<n;i++){
ll tmp=x+1ll*y*(v[i].S-v[i].F);
if(s.size()==||(*s.begin()).F>=v[i].F){
ans+=tmp;
ans%=mod;
continue;
}
multiset<pii>::iterator it=s.lower_bound({v[i].F,-});
it--;
if(tmp<=1ll*y*(v[i].S-(*(it)).F)){
ans+=tmp;
ans%=mod;
continue;
}
ans+=1ll*y*(v[i].S-(*(it)).F);
ans%=mod;
s.erase(it);
}
cout<<ans<<endl; return ;
}
上一篇:LINUX下CDT和EDT时区的切换


下一篇:Appium+python自动化13-native和webview切换