挑战程序设计竞赛》P345 观看计划

《挑战程序设计竞赛》P345 观看计划

题意：一周一共有M个单位的时间。一共有N部动画在每周si时开始播放,ti时刻播放结束，问每周最多能看多少部动画。

思路：贪心+倍增法

可以看成一个圆周上有N个区间,找出N个区间中尽可能多的互不相交的区间。选定一个区间作为起始区间后,贪心思想是：每次尽量选取与当前区间不重合且结束时间最早的区间。

那么贪心策略还可以这样考虑，对于某区间i，选择区间j满足（i的结束时间t[i]<j的开始时间s[j]）,从这些j中选择一个结束时间最早区间(记为k)作为区间i的下一个区间，记为next[i]=k;

有了next数组即可倍增来优化了,譬如next[1][i]=j,next[1][j]=k,则next[2][i]=k,意为i跨两个区间可以到达区间k.

参考代码：

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<algorithm>

#include<vector>

#include<cstring>

#include<string>

#include<cmath>

using namespace std;

#define INF 0x3f

#define N_MAX 100000+20

#define NLOG 30

pair<int, int>ps[*N_MAX];

int s[N_MAX*+],t[N_MAX*+];

int Next[NLOG][N_MAX];

int n, m;

bool cmp(const pair<int,int>p1,const pair<int,int>p2) {

    if (p1.first != p2.first)return p1.first < p2.first;

    else return p1.second > p2.second;//若某一个区间头部和另一个区间的尾部时间点重合，尾部在前！！

}

int main() {

    while (scanf("%d%d",&n,&m)!=EOF) {

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

            scanf("%d%d",&s[i],&t[i]);

        }

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

            if (s[i] > t[i])t[i] += m;

            s[i + n] = s[i] + m;

            t[i + n] = t[i] + m;

        }

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

            ps[i] = make_pair(s[i], i);//区间头部

            ps[i+*n] = make_pair(t[i], i+*n);//区间尾部

        }

        sort(ps, ps +  * n,cmp);

        int last = -;

        memset(Next,-,sizeof(Next));

        for (int i = *n-; i >=;i--) {//!!!!!

            int id = ps[i].second;

            if (id <  * n) {

                if (last == - || t[last] > t[id]) last = id;

            }

            else {

                id -=  * n;

                Next[][id] = last;

            }

        }

        for (int k = ; k +< NLOG;k++) {

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

                if (Next[k][i] == -)Next[k + ][i] = -;

                else

                    Next[k + ][i] = Next[k][Next[k][i]];

            }

        }

        int max_cnt = ;

        for (int i = ; i < n;i++) {//选定一个初始城市

            int j = i,cnt=;//j代表当前所在城市

            for (int k = NLOG - ; k >= ;k--) {

                if (Next[k][j] >=  && t[Next[k][j]] <= s[i] + m) {

                    j = Next[k][j];

                    cnt |=  << k;

                }

            }

            max_cnt = max(max_cnt, cnt+);//不要忘了一开始选为起点的区间

        }

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

    }

    return ;

}

巴特西

挑战程序设计竞赛》P345 观看计划

最新文章

热门文章