Educational Codeforces Round 27-C. Two TVs

xiaoxiao2021-02-28  66

题意:Polycarp有两台电视,他想看一些电视节目,他知道一些电视开始和结束的时间,现在他想知道有两台电视他能不能播放所有的节目,注意:一个节目结束的时间不能播放其他节目。

思路:把电视节目的开始和结束时间都拆成两个部分,分别标记一些,在根据增序进行排序,遍历结束和开始时间,用一个cnt进行维护,如果出现cnt>2,则不能播放所有的节目。

#include <bits/stdc++.h> using namespace std; const int maxn=4e5+10; struct Node { int mark; int t; } node[maxn]; bool cmp(Node n1,Node n2) { return n1.t<n2.t||(n1.t==n2.t&&n1.mark>n2.mark); } int main() { int n; cin>>n; int cnt=0; for(int i=1; i<=n; i++) { int l,r; cin>>l>>r; node[cnt].mark=1; node[cnt++].t=l; node[cnt].mark=-1; node[cnt++].t=r; } int ans=0; sort(node,node+cnt,cmp); for(int i=0; i<cnt; i++) { ans+=node[i].mark; if(ans>2) { cout<<"NO"<<endl; return 0; } } cout<<"YES"<<endl; }
转载请注明原文地址: https://www.6miu.com/read-2622314.html

最新回复(0)