POJ-2376 Cleaning Shifts

曾经终败给现在 2023-06-01 08:47 5阅读 0赞

1 #include <iostream>
     2 #include <algorithm>
     3 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     4 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     5 #define INF 0x3f3f3f3f
     6 typedef long long ll;
     7 using namespace std;
     8 inline ll read()
     9 {
    10     ll ans = 0;
    11     char ch = getchar(), last = ' ';
    12     while(!isdigit(ch)) last = ch, ch = getchar();
    13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    14     if(last == '-') ans = -ans;
    15     return ans;
    16 }
    17 inline void write(ll x)
    18 {
    19     if(x < 0) x = -x, putchar('-');
    20     if(x >= 10) write(x / 10);
    21     putchar(x % 10 + '0');
    22 }
    23 struct section
    24 {
    25     int l;
    26     int r;
    27     bool operator < (section b)
    28     {
    29         if(l != b.l)
    30             return l < b.l;
    31         return r < b.r;
    32     }
    33 };
    34 int N,T;
    35 section a[25003];
    36 int main()
    37 {
    38     N = read(),T = read();
    39 
    40     _for(i,1,N+1)
    41         a[i].l = read(),a[i].r = read();
    42     
    43     sort(a+1,a+N+1);
    44     
    45     int l = 0,i = 0;
    46     int rnt = 0;
    47     while(l < T)
    48     {
    49         int maxr = -1;
    50         while(a[++i].l <= l+1 && i < N+1)
    51             maxr = max(maxr,a[i].r);
    52         if(i > N+1)
    53             break;
    54         if(maxr==-1)    {printf("-1\n");return 0;}
    55         rnt ++;
    56         i --;
    57         l = maxr;
    58     }
    59     printf("%d\n",rnt);
    60     return 0;
    61 }

转载于:https://www.cnblogs.com/Asurudo/p/11393507.html

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj2376(贪心)

题目：给定一个时间T和N个时间区间，求最少需要多少个区间覆盖总区间\[1,T\]，无法覆盖区域\[1,T\]时输出-1。 Description Farmer John

浅浅的花香味﹌/ 2024年02月17日 21:39/ 0 赞/ 78 阅读

相关 [USACO 05 DEC]Cleaning Shifts

题面描述约翰的奶牛们从小娇生惯养，她们无法容忍牛棚里的任何脏东西。约翰发现，如果要使这群有洁癖的奶牛满意，他不得不雇佣她们中的一些来清扫牛棚，约翰的奶牛中有\\(N(1

约定不等于承诺〃/ 2023年08月17日 17:38/ 0 赞/ 63 阅读

相关 POJ 2376

题意略。思路：本题有几个坑： 1.\[1,5\] , \[6,10\] 是对 \[1,10\] 的全覆盖，所以我们要把区间变为\[1,6)和\[6,11)，最后判断连

小咪咪/ 2023年08月17日 16:37/ 0 赞/ 98 阅读

相关 POJ-2376 Cleaning Shifts

1 include <iostream> 2 include <algorithm> 3 define _for(i,a,b) for(int i

曾经终败给现在/ 2023年06月01日 08:47/ 0 赞/ 6 阅读

相关 - Cleaning Shifts

Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chore

超、凢脫俗/ 2022年06月12日 06:27/ 0 赞/ 146 阅读

相关 poj-2376-Cleaning Shifts

Cleaning Shifts <table> <tbody> <tr> <td><strong>Time Limit:</strong> 100

我会带着你远行/ 2022年05月20日 05:56/ 0 赞/ 144 阅读

相关 Cleaning Shifts（POJ_2376) 【贪心、区间】

Description: Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some

Dear 丶/ 2022年05月18日 01:35/ 0 赞/ 161 阅读

相关 Cleaning Shifts POJ - 2376 (区间贪心,覆盖问题)

Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chore

╰+攻爆jí腚メ/ 2022年03月09日 00:12/ 0 赞/ 250 阅读

相关 POJ 3171 Cleaning Shifts 题解《挑战程序设计竞赛》

[为什么80%的码农都做不了架构师？>>> ][80_] ![hot3.png][] ![POJ 3171 Cleaning Shifts 题解《挑战程序设计竞赛》][

刺骨的言语ヽ痛彻心扉/ 2022年01月15日 10:39/ 0 赞/ 222 阅读

相关 [转] Covariate shift && Internal covariate shift

from: [https://www.kaggle.com/pavansanagapati/covariate-shift-what-is-it][https_www.kagg

红太狼/ 2022年01月05日 05:37/ 0 赞/ 250 阅读