首页 > 其他 > 详细

E - Cleaning Shifts POJ - 2376

时间:2020-03-21 22:04:46      阅读:56      评论:0      收藏:0      [点我收藏+]

贪心,有一些点少不留意就会wa

#include <iostream>
#include <cstdio>
#include <cstring>
#include <limits>
//#include <stack>
#include<queue>
#include <algorithm>
#define endl ‘\n‘
#define _for(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int N = 1e5+5;
typedef long long ll;
int n,t;
struct Node{
    int l,r;
    bool operator < (const Node &o)const{
        if( l!= o.l ) return l<o.l;
        return r > o.r;
    }
}a[N]; 
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>t;
    _for(i,0,n){
        cin>>a[i].l>>a[i].r;
        if( a[i].l > a[i].r ) swap( a[i].l,a[i].r );
    }
    sort(a,a+n);
    int pos = 1,R = a[0].r,cnt = 1;
    while(R<t){
        int flag = 0,M = R;
        while( pos<n && a[pos].l <= R+1 ) M = max(M,a[pos].r),pos++,flag = 1;
 
        if( flag ==0 || M<= R  ) break; 
        R = M;
        cnt++;
    }
    if( a[0].l>1 || R<t ){
        cout<<-1<<endl;
        return 0;
    }
    else cout<<cnt<<endl; 
    return 0;
}

 

E - Cleaning Shifts POJ - 2376

原文:https://www.cnblogs.com/SunChuangYu/p/12542003.html

(1)
(1)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!