救生员
题目 救生员
思路分析
首先想到用差分
雇用一头牛等于在一段里面++ 解雇一头牛等于--
存入所有的l,r 再枚举减去某一种的情况
分别构造前缀和 最后看非0的个数即可
这道题还有一个数据范围更大的版本
于是想到了用离散化 因为只需要用到的牛 不需要把整个数据范围构造前缀和
但是还是会tle
其实时间花在了每次移除一头牛 就要重新构造一次前缀和 这显然浪费时间 而且还有n次二分查找找映射位置
错的不冤（不过这也意味着现在能知道差分和离散化的用法场景了 也还不错）
然后也不难发现可以用区间合并
难点就在于 我怎么每次只挑几个做合并
因为这种操作不可逆 你想先合并了再删掉某段 答案会有问题
所以只能每次少挑一个做合并
这怎么办?
很巧妙的地方就是
两重for循环
当j=i的时候 我就不添加呗 这样其他的就都做了合并
每轮只有一个没做合并 等同于被删掉
(虽然这种在数据范围变大后也会tle emmm)
代码实现
差分
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
typedef pair<int,int> PII;
vector<PII> cows;
int b[N],s[N];
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++){
int l,r;
cin>>l>>r;
cows.push_back({l,r});
b[l+1]++;
b[r+1]--;
}
int res=0;
for(auto cow:cows){
int num=0;
int l=cow.first,r=cow.second;
b[l+1]--;
b[r+1]++;
for(int i=1;i<N;i++){
s[i]=s[i-1]+b[i];
if(s[i]>0)
num++;
}
res=max(res,num);
b[l+1]++;
b[r+1]--;
}
cout<<res<<endl;
return 0;
}
数据范围变大后的离散化+差分
https://www.acwing.com/problem/content/description/1748/
虽然tle了 但是思路自卖自夸一下
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
vector<PII> cows;
vector<int> alls;
int b[N],s[N];
int n;
int find(int x){
int l=0,r=alls.size()-1;
while(l<r){
int mid=l+r>>1;
if(alls[mid]>=x)
r=mid;
else
l=mid+1;
}
return r+1;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++){
int l,r;
cin>>l>>r;
cows.push_back({l,r});
alls.push_back(l);
alls.push_back(r);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(auto cow:cows){
int l=find(cow.first),r=find(cow.second);
b[l]++;
b[r]--;
}
int res=0;
for(auto cow:cows){
int num=0;
int l=find(cow.first),r=find(cow.second);
b[l]--;
b[r]++;
for(int i=1;i<alls.size();i++){
s[i]=s[i-1]+b[i];
if(s[i]>0)
num+=alls[i]-alls[i-1];
}
res=max(res,num);
//还原现场
b[l]++;
b[r]--;
}
cout<<res<<endl;
return 0;
}
区间合并
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
typedef pair<int,int> PII;
vector<PII> cows;
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++){
int l,r;
cin>>l>>r;
cows.push_back({l,r});
}
sort(cows.begin(),cows.end());
int res=0;
for(int i=0;i<n;i++)
{
int sum=0,st=-1,ed=-1;
for(int j=0;j<n;j++)
{
if(i!=j)
{
if(ed<cows[j].first)
{
if(ed!=-1)
sum+=ed-st;
st=cows[j].first,ed=cows[j].second;
}
else if(ed<cows[j].second)
ed=cows[j].second;
}
}
if(ed!=-1)
sum+=ed-st;
res=max(sum,res);
}
cout<<res<<endl;
return 0;
}
💬 评论