艺(贪心)

描述

传送门:牛客小白月赛2-I

 接下去,Sεlιнα(Selina) 又搞了个文艺竞演。
虽说是文艺竞演,其实只是为了满足 Sεlιнα 的内心企盼——看群男友献歌献舞。她排列好了各个参赛男友的节目顺序,然后将他们安排在两个舞台上表演,自己则在演播室里使用两台闭路电视同时观看。万万没想到的是,当一切准备就绪时,其中一台电视炸了,她不会修,也没有时间修。于是只能尴尬地使用一台闭路电视观看两个舞台上的节目。当然,这台电视不支持分屏同时观看,所以 Sεlιнα 只能不停地换台观看。现在,作为导演的 Sεlιнα 已经知道了两个舞台的节目 单以及每个节目$i$对于她所能产生的愉悦度$v_i$,她想安排电视在每个时刻播放的频道(可以在某些时刻不看),使得自己能得到最大的愉悦度。现在请优秀的你告诉 Sεlιнα 最大能产生的愉悦度是多少。
要注意的是,文艺竞演没有广告插播,所以当一个节目结束时,另一个节目会立刻开始演出。 并且 Sεlιнα 看节目以分钟为单位,也就是说,她只能在每分钟结束的那一刻切换舞台。节目对 Sεlιнα 产生愉悦度是以分钟为单位的,也就是说,她看第$i$个节目每一分钟就会产生$v_i$的愉悦度。而 Sεlιнα 对节目的完整性丝毫不在意,没有完整地看一个节目是没有关系的。

Input

第一行三个数$N,M,T$,表示舞台一有$N$个节目,舞台二有$M$个节目,总时长为$T$分钟。
接下去$N$行,每行两个整数$x_i,v_i$,表示舞台一的第$i$个节目在第$x_i$分钟结束后开始,每分钟能产生愉悦度$v_i$。当一个节目开始时,这个舞台之前正在播放的节目直接停止,中间没有暂停。
接下去$M$行,每行两个整数$x_j,v_j$,表示舞台二的第$j$个节目在第$x_j$分钟结束后开始,每分钟能产生愉悦度$v_j$。当一个节目开始时,这个舞台之前正在播放的节目直接停止,中间没有暂停。
数据保证每个舞台都有一个在$0$分钟时开始的节目(即最开始的节目),并且在同一个舞台中没有两个节目开始时间相同(即没有一个节目时长为$0$。数据不保证输入中每个舞台的$x_i$会从小到大排序。
$1≤N,M≤10^5$
$1≤Y≤10^9$
$-100≤V_i≤100$

Output

输出共一行,一个整数,表示最大的愉悦度。

Examples

  • intput

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    2 2 5
    2 3
    0 2
    0 3
    3 1
    3 4 17
    8 3
    0 10
    9 10
    7 15
    0 6
    16 9
    14 8
  • output

    1
    2
    15
    205

思路

  • 先按开始时间排序。
  • 对于每个时间点,都在两个频道中选一个愉悦值大的。
  • 选定一个频道之后,ans就加一个区间$\times $选的愉悦值,这个区间就是两个频道的节目都没变的时间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e5+5;
typedef long long ll;

struct node{
int l,w;
bool operator<(node e) const{
return l<e.l;
};
}a[N],b[N];

int main()
{
int N,M,T,x,y;

scanf("%d%d%d",&N,&M,&T);
rep(i,0,N) scanf("%d%d",&a[i].l,&a[i].w);
sort(a,a+N);

rep(i,0,M) scanf("%d%d",&b[i].l,&b[i].w);
sort(b,b+M);

int na=0,nb=0,nmax=-10000;ll sum=0; // na/nb:当前是a/b频道的第几个节目
for(int i=0;i<T;){ //i:当前时间
if(na+1<N&&i==a[na+1].l) na++;
if(nb+1<M&&i==b[nb+1].l) nb++;

nmax=max(a[na].w,b[nb].w);
if(nmax>0) sum+=nmax*(min(na+1<N? a[na+1].l:T,nb+1<M? b[nb+1].l:T)-i);//加当前到下一个节目开始的时间。如果是最后一个节目就取T
i=min(na+1<N? a[na+1].l:T,nb+1<M? b[nb+1].l:T);
}
printf("%lld\n",sum);
return 0;
}
-------------本文结束 感谢您的阅读-------------

本文标题:艺(贪心)

文章作者:Armin

发布时间:2019年01月11日 - 01:01

最后更新:2019年01月11日 - 11:01

原始链接:http://x-armin.com/艺/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

小礼物走一波