看直播 csust oj

看直播

Description

小明喜欢看直播，他订阅了很多主播，主播们有固定的直播时间 [Li, Ri] 。

可是他网速只有2M，不能同时播放两个直播，所以同一时间只能看一个直播。

并且他只会去看能完整看完的直播（从开播到停播都能观看）。

他想知道最多能看多长时间的直播呢？

注意 [1, 3] 和 [3, 4] 不能两者都选择。

Input

第一行一个N。

接下来N行每行两个整数Li, Ri。

1 <= N <= 2e5

1 <= Li <= Ri <= 1e9

Output

输出最多能看的时间。

Sample Input 1

Sample Output 1

这个题目不是特别难，可以用很多方法写。

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

const int maxn = 4e5 + ;

struct node

{

    ll l, r, com;

    node(ll l=,ll r=,ll com=):l(l),r(r),com(com){}

}ex[maxn];

ll dp[maxn], a[maxn];

struct edge

{

    int ed, w;

    edge(int ed=,int w=):ed(ed),w(w){}

};

vector<edge>e[maxn];

int main()

{

    int n, tot = ;

    scanf("%d", &n);

    for(int i=;i<=n;i++)

    {

        int l, r;

        scanf("%d%d", &l, &r);

        ex[i] = node(l, r, );

        a[++tot] = l;

        a[++tot] = r;

    }

    sort(a + , a +  + tot);

    int len = unique(a + , a +  + tot) - a - ;

    for(int i=;i<=n;i++)

    {

        ex[i].com = ex[i].r - ex[i].l + ;

        ex[i].l = lower_bound(a + , a +  + len, ex[i].l) - a;

        ex[i].r = lower_bound(a + , a +  + len, ex[i].r) - a;

        e[ex[i].l].push_back(edge(ex[i].r,ex[i].com));

    }

    for(int i=len;i>=;i--)

    {

        dp[i] = dp[i + ];

        for(int j=;j<e[i].size();j++)

        {

            edge x = e[i][j];

            dp[i] = max(dp[i], dp[x.ed + ] + x.w);

        }

    }

    printf("%lld\n", dp[]);

    return ;

}

纯dp

Dragon plus ::

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#define fir first

#define sec second

using namespace std;

typedef pair<int,int> P;

const int maxn = 2e5+;

int n,len;

P s[maxn];

int v[maxn<<];

int Max[maxn<<];

bool cmp(const P& a,const P& b) {

    return a.sec<b.sec;

}

void pushup(int num) {Max[num] = max(Max[num<<],Max[num<<|]);}

void build(int l,int r,int num) {

    if(l==r) {

        Max[num]=;

        return ;

    }

    int mid = (l+r) >>;

    build(l,mid,num<<);

    build(mid+,r,num<<|);

    pushup(num);

}

void modify(int l,int r,int num,int pos,int mods) {

    if(pos<l || r <pos) return ;

    if(pos<=l&&r<=pos) {

        Max[num] = max(Max[num],mods);

        return ;

    }

    int mid = (l+r) >>;

    if(pos<=mid) modify(l,mid,num<<,pos,mods);

    if(mid< pos) modify(mid+,r,num<<|,pos,mods);

    pushup(num);

}

int quriy(int l,int r,int num,int le,int ri) {

    if(ri<l || r<le) return ;

    if(le<=l && r<=ri) return Max[num];

    int mid = (l+r) >>;

    int ans = ;

    if(le<=mid) ans = max(ans,quriy(l,mid,num<<,le,ri));

    if(mid< ri) ans = max(ans,quriy(mid+,r,num<<|,le,ri));

    return ans;

}

int main() {

    int now =;

    scanf("%d",&n);

    for(int i=;i<n;i++) {

        scanf("%d%d",&s[i].fir,&s[i].sec);

        v[now++] = s[i].fir;

        v[now++] = s[i].sec;

    }

    sort(v,v+now);

    sort(s,s+n,cmp);

    len = unique(v,v+now)-v;

    build(,len,);

    for(int i=;i<n;i++) {

        int res = s[i].sec -s[i].fir+;

        int d = lower_bound(v,v+len,s[i].fir)-v;

        int d2 = lower_bound(v,v+len,s[i].sec)-v+;

        res += quriy(,len,,,d);

        modify(,len,,d2,res);

    }

    printf("%d\n",quriy(,len,,,len));

    return ;

}

dp+线段树

#include <iostream>

#include <algorithm>

#include <cstdio>

#define fir first

#define sec second

using namespace std;

typedef pair<int,int> P;

const int maxn = 2e5+;

bool cmp(const P&a,const P&b) {

    return a.sec<b.sec;

}

int n,lst;

P s[maxn];

int dp[maxn<<];

int v[maxn<<];

int p[maxn];

int main() {

    int now = ;

    scanf("%d",&n);

    for(int i=;i<n;i++) {

        scanf("%d%d",&s[i].fir,&s[i].sec);

        v[now++]=s[i].fir;

        v[now++]=s[i].sec;

    }

    int ans = ;

    sort(v,v+now);

    sort(s,s+n,cmp);

    int len = unique(v,v+now)-v;

    for(int i=;i<n;i++) {

        int d = s[i].sec - s[i].fir+;

        int l = lower_bound(v,v+len,s[i].fir)-v;

        int r = lower_bound(v,v+len,s[i].sec)-v;

        int Max = lower_bound(p,p+lst+,l)-p-;

        //cout<<p[Max]<<' '<<dp[p[Max]]<<endl;

        dp[r] = max(dp[r],dp[p[Max]]+d);

        ans = max(dp[r],ans);

        //cout<<r<<' '<<dp[r]<<' '<<lst<<endl;

        if(dp[p[lst]] >= dp[r]) continue;

        else {

            if(p[lst] != r) p[++lst] = r;

        }

    }

    printf("%d\n",ans );

    return ;

}

CSUST Online Judge

Powered by OnlineJudge   Version: -ed4d6

dp+单调队列

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e5 + ;

struct date {

    int le, ri;

} a[MAX];

int lsh[MAX * ];

bool cmp(date A, date B) {

    if (A.le != B.le) {

        return A.le < B.le;

    }

    else {

        return A.ri < B.ri;

    }

}

int dp[MAX * ];

int s[MAX * ];

int main() {

    int n;

    scanf("%d", &n);

    int cnt = ;

    for (int i = ; i <= n; i++) {

        scanf("%d%d", &a[i].le, &a[i].ri);

        lsh[++cnt] = a[i].le;

        lsh[++cnt] = a[i].ri;

    }

    sort(lsh + , lsh + cnt + );

    cnt = unique(lsh + , lsh + cnt + ) - lsh - ;

    sort(a + , a + n + , cmp);

    for (int i = ; i <= n; i++) {

        a[i].le = lower_bound(lsh + , lsh + cnt + , a[i].le) - lsh;

        a[i].ri = lower_bound(lsh + , lsh + cnt + , a[i].ri) - lsh;

    }

    int k = ;

    int top = , tail = ;

    for (int i = ; i <= cnt && k <= n; i++) {

        while (i == a[k].le) {

            dp[a[k].ri] = max(dp[a[k].ri], lsh[a[k].ri] - lsh[a[k].le] + s[top] + );

            k++;

        }

        while (top <= tail && s[tail] <= dp[i]) {

            tail--;

        }

        s[++tail] = dp[i];

    }

    int ans = ;

    for (int i = ; i <= cnt; i++) {

        ans = max(ans, dp[i]);

    }

    printf("%d\n", ans);

    return ;

}

dp+单调队列

巴特西

看直播 csust oj

最新文章

热门文章