POJ 2376

小咪咪 2023-08-17 16:37 98阅读 0赞

题意略。

思路：

本题有几个坑：

1.\[1,5\] , \[6,10\] 是对 \[1,10\] 的全覆盖，所以我们要把区间变为\[1,6)和\[6,11)，最后判断连续区间右端是否大于T。

2.牛的工作时间可能会超过T，要及时跳出循环。

3.区间有可能左端没有覆盖到1。

代码如下：

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn = 25005;
    
    struct seg{
        int l,r;
        seg(int l = 0,int r = 0){
            this->l = l,this->r = r;
        }
    };
    
    int N,T;
    seg store[maxn];
    
    bool cmp(const seg& s0,const seg& s1){
        if(s0.l != s1.l) return s0.l < s1.l;
        return s0.r > s1.r;
    }
    
    int main(){
        scanf("%d%d",&N,&T);
        int l,r;
        for(int i = 0;i < N;++i){
            scanf("%d%d",&l,&r);
            r += 1;
            store[i] = seg(l,r);
        }
        
        sort(store,store + N,cmp);
        int rbound = -1,ans = 0,lft,rmax,i;
        for(i = 0,rmax = store[0].r,lft = store[0].l;i < N;++i){
            l = store[i].l,r = store[i].r;
            if(rbound == -1 || l > rbound){
                ++ans;
                rbound = rmax;
            }
            if(rbound > T || rbound < l) break;
            rmax = max(rmax,r);
        }
        if(lft > 1 || rmax <= T) ans = -1;
        else if(rbound <= T && rmax > T) ans += 1;
        
        printf("%d\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/tiberius/p/11509754.html

发表评论取消回复

表情：

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

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

相关阅读

相关 poj2376(贪心)

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

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

相关 POJ 2376

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

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

相关 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 阅读

相关 poj 1064 java_poj1064

Cable master Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 15127 Accept

r囧r小猫/ 2022年11月05日 03:30/ 0 赞/ 204 阅读

相关【POJ】：POJ 3984

题目链接：[http://poj.org/problem?id=3984][http_poj.org_problem_id_3984] 题目解析：这题算是搜索里面的简单题了吧

Myth丶恋晨/ 2022年08月23日 04:50/ 0 赞/ 221 阅读

相关 poj1321+poj2251

poj1321代码实现（dfs）： include <iostream> include <string.h> using namespace std

心已赠人/ 2022年05月30日 04:08/ 0 赞/ 206 阅读

相关 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 赞/ 162 阅读

相关 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 阅读

相关 poj1007

1．链接地址 [https://vjudge.net/problem/POJ-1007][https_vjudge.net_problem_POJ-1007] 2．问题描述

深藏阁楼爱情的钟/ 2021年11月23日 15:38/ 0 赞/ 235 阅读