Codeforces 845C. Two TVs 思路：简单贪心算法

题目：

题目原文链接：http://codeforces.com/contest/845/problem/C

题意：现在我们有一个电视清单，有两个电视，电视清单上有每一个节目的开始时间和结束时间。

　　　电视不能接连不间断的播放，例如TV1播放完1-2点的节目后不能接着播放2-3点的电视，除非在TV2上播放，如果TV2也正在播放则不能播放完清单。

思路：

　　1.对清单排序，让开始时间早的靠前，如果开始时间相同，结束时间早的靠前。

　　2.如果TV1已经结束。就把这一个节目的结束时间赋给TV1，然后看下一个节目。

　　3.如果TV1尚未结束，TV2已经结束。就把这一个节目的结束时间赋给TV2，然后看下一个节目。

　　4.如果TV1、TV2都尚未结束。就输出NO，不再看下一个节目。

代码：

#include <bits\stdc++.h>

using namespace std;

struct node{

    int l;int r;

}a[];

bool cmp(node a,node b){

    if(a.l == b.l) return a.r < b.r;

    return a.l < b.l;

}

int main(){

    int n;

    cin >> n;

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

        cin >> a[i].l >> a[i].r;

    }

    sort(a,a+n,cmp); //对清单排序，让开始时间早的靠前，如果开始时间相同，结束时间早的靠前。 

    int r1 = -,r2 = -;  //初始化上一个节目结束的时间

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

        if(r1 < a[i].l){  //如果TV1已经结束。就把这一个节目的结束时间赋给TV1，然后看下一个节目。

          r1 = a[i].r;

          continue;

        }

        if(r2 < a[i].l){  //如果TV1尚未结束，TV2已经结束。就把这一个节目的结束时间赋给TV2，然后看下一个节目。

            r2 = a[i].r;

            continue;

        }

        cout << "NO" << endl;//如果TV1、TV2都尚未结束。就输出NO，不再看下一个节目。

        return ;

    }

    cout << "YES" << endl;

    return ;

}

巴特西

Codeforces 845C. Two TVs 思路：简单贪心算法

最新文章

热门文章