OpenJ_Bailian-2376 Cleaning Shifts

题面

【VJudge】 【OpenJudge 百练】

给你N,T,再给你N个区间,求最少选择多少个区间能覆盖[1,T]之间所有的整数位置
N <= 25000, T <= 1000000

总结

这题我一开始因为自己之前对贪心的不重视和刷题量少，所以一直没想出来QAQ。

然后就是正解了：我们先看一下这几个数据：

5 10
1 4
2 3
3 9
4 7
6 10

因为我们要求出最少的完全覆盖的区间，所以当我们知道一个子区间的起点的时候，要去取出起点最靠近上一个子区间的终点向右侧移动一格的那格且在该格子的左边的那个右端点最右的，所以我们按照子区间的起点排序

我们先去取第一个（排序后左端点最左这样可以完全覆盖开头的点）1 4
对于2 3，因为右端点小于4，舍去。
对于3 9和4 7，因为3 9的右端点更大（这样可以包括更大的空间），我们选择3 9。
然后是6 10，因为上一次遍历的时候这是第一个比4大的点，我们可以想当然地停止搜索（这就是按照左端点排序的优势——可以保证之后的每一个点都比上一个子区间的右端点大从而不能完整覆盖，判定停止的方法就简单了很多）。
接下来是新的遍历，因为这是唯一一个点了（那是当然的，最重要的是看其左端点是不是小于9），将其收入囊中。
因为最后一个点10也正好被覆盖，游戏结束。

槽点

1. (TLE) 犯了三个严重的错误：
   1. ai的初始化错误
   2. 终止条件bi<ai应为bi<=ai
   3. 忘了将b赋值给ai以至于死循环

   反正就是天上掉下了个死循环。

AC代码

#include<bits/stdc++.h>
using namespace std;
pair<int,int> st[30000];
int n,t,a,b,c,ai,bi,ans=0;
int main(){
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a,&b);
        st[i]=make_pair(a,b);
    }
    sort(st+1,st+1+n);
    /*for(int i=1;i<=n;i++){
        printf("%d %d\n",st[i].first,st[i].second);
    }*/
    a=0,ai=0,b=0,bi=1;
    while(a<t){
        b = 0;
        bi = upper_bound(st+1,st+n+1,make_pair(a+2,a+2))-st-1;
        //cout<<"Found "<<bi<<" : ( "<<st[bi].first<<" , "<<st[bi].second<<" ) , and ai = "<<ai<<endl;
        if(bi<=ai){
            printf("-1\n");
            return 0;
        }
        for(int i=ai;i<=bi;i++){
            if(st[i].second>st[b].second){
                b=i;
            }
        }
        a=st[b].second;
        ai = b;                             //--------add 1
        ans++;
        //cout<<"a = "<<a<<endl;
    }
    printf("%d\n",ans);
    return 0;
}

页面： 1 2 3