头条最后一题,不知道思路对不对,有测试用例吗?
笔试思路歪了,最后两分钟突然有个思路不知道对不对,正在写代码接到了百度的电面。。。刚面完,附上代码。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M;
cin>>N>>M;
using namespace std;
int main(){
int N,M;
cin>>N>>M;
//一天分为M段,看直播为1,没看直播为0
vector<int> vec(M,0);
vector<int> vec(M,0);
//临时数组,记录前一次状态
vector<int> tv(M,0);
multimap<int,pair<int,int> >mp;
while(N--){
int tmp1,tmp2,t;
cin>>tmp1>>tmp2;
t = tmp2-tmp1;
vector<int> tv(M,0);
multimap<int,pair<int,int> >mp;
while(N--){
int tmp1,tmp2,t;
cin>>tmp1>>tmp2;
t = tmp2-tmp1;
//按每个直播的时间长度排序
t>0?mp.emplace(t,make_pair(tmp1,tmp2)):mp.emplace(M-tmp1+tmp2,make_pair(tmp1,tmp2));
}
int ans = 0;
for(auto i = mp.begin();i != mp.end();i++){
t>0?mp.emplace(t,make_pair(tmp1,tmp2)):mp.emplace(M-tmp1+tmp2,make_pair(tmp1,tmp2));
}
int ans = 0;
for(auto i = mp.begin();i != mp.end();i++){
tv = vec;////备份当前状态
bool out = false;
int l = i->second.first;
int r = i->second.second;
bool out = false;
int l = i->second.first;
int r = i->second.second;
//如果跨天了
if(i->second.first > i->second.second){
ans++;
while(l < M){
if(vec[l] == 1){
vec = tv;//
out = true;
ans--;
break;
}
vec[l] = 1;
l++;
}
if(out)continue;
while(r > 0){
if(vec[r-1] == 1){
vec = tv;
out = true;
ans--;
break;
}
vec[r-1] = 1;
r--;
}
}else{ //没跨天
ans++;
while(l < r){
if(vec[l] == 1){
vec = tv;
ans--;
break;
}
vec[l] = 1;
l++;
}
}
}
cout<<ans;
return 0;
}
#测试#if(i->second.first > i->second.second){
ans++;
while(l < M){
if(vec[l] == 1){
vec = tv;//
out = true;
ans--;
break;
}
vec[l] = 1;
l++;
}
if(out)continue;
while(r > 0){
if(vec[r-1] == 1){
vec = tv;
out = true;
ans--;
break;
}
vec[r-1] = 1;
r--;
}
}else{ //没跨天
ans++;
while(l < r){
if(vec[l] == 1){
vec = tv;
ans--;
break;
}
vec[l] = 1;
l++;
}
}
}
cout<<ans;
return 0;
}