oiClass

P2148 打扫卫生O(T)

by 2021tyoi0037——2022-04-16 17:02:32

**题外话：**
看到本题解法多是`O(NlogN)`，想分享一下我的`O(T)`解法
~~时间复杂度不更高吗~~

---
这道题，用脚趾想都是**贪心题**，不过具体的贪心思路还得多思考
肯定是能接班的人手接班，在此条件下，能加班到越久越好
我们用类似**dp**的思想来写一个预处理吧
定义**f_i**为i时间以前的模范打工人（**f_i**为零表示此阶段没有打工人空闲）

cin>>n>>t;
    for(int i=1;i<=n;i++){
    	cin>>si>>ei;
    	f[si]=max(f[si],ei);
    }
    for(int i=1;i<=t;i++) f[i]=max(f[i],f[i-1]);

写完以后按题意模拟就好了
但有一点要注意，我们要注意有人的结束比自己结束还早就接班，以及自己接自己的班肯定是不允许的 （都干完了你接什么班）
完整的代码如下：

#include <iostream>
    #include <queue>
    #include <cstdio>
    #define int long long
    using namespace std;
    
    //贪心，能接班的人手接班，在此前提下能加班到越久越好
    //在此用dp标记i阶段(i以前)中谁是最佳打工人
    int n,t,si,ei,st=1,ans,f[1000001];
    signed main(){
    	cin>>n>>t;
    	for(int i=1;i<=n;i++){
    		cin>>si>>ei;
    		f[si]=max(f[si],ei);
    	}
     for(int i=1;i<=t;i++) f[i]=max(f[i],f[i-1]);
     //此时f[i]存的是i阶段中最佳打工人
    	//f[i]为0表示没有打工人这个时候接班，直接倒闭
    	//st表示最晚开始点
    	while(st<=t){//干到t就成功下班吧（如果下一个的开始点在t+1就下班）
    		if(f[st]>=st) st=f[st]+1;//st前（包括st）的最佳打工人接班
    		else{//没有打工人接班，完蛋
    			cout<<-1;
    			return 0;
    		}
    		ans++;
    	}
    	cout<<ans;
    	return 0;
    }

---
有异议请各位巨佬补充