暴力只过了三个数据点,这题想要ac是很难的,很多细节要注意,区间合并也是头一次见
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int li[N],si[N];
bool hhh[N];
int n,len;
bool check(int mid)
{
//int small=1e9+1;
// int big=-1;
int da=-1,xiao=-1;
memset(hhh,0,sizeof(hhh));
for(int i=1;i<=n;i++)
{
if(si[i]>mid)
{
continue;
}
da=li[i]+mid-si[i];
xiao=li[i]-(mid-si[i]);
for(int j=xiao;j<=da;j++)
{
hhh[j]=1;
}
/* if(xiao<0)
{
xiao=0;
}*/
// small=min(xiao,small);
// big=max(da,big);
}
//cout<<small<<" "<<big<<'\n';
/*if(small<=1&&big>=len)
{
return 1;
}else
{
return 0;
}*/
for(int i=1;i<=len;i++)
{
if(hhh[i]==0)
{
return 0;
}
}
return 1;
}
signed main()
{
cin>>n>>len;
for(int i=1;i<=n;i++)
{
cin>>li[i]>>si[i];
}
int l=1,r=1e5;
while(l<r)
{
//cout<<l<<" "<<r<<endl;
int mid=(l+r)/2;
//cout<<mid<<endl;
if(check(mid))
{
r=mid;
}else
{
l=mid+1;
}
//cout<<l<<" "<<r<<endl;
}
cout<<l;
return 0;
}
构建动态数组,排序处理
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
int li[N],si[N];
int n,len;
bool check(int mid)
{
vector<PII> sb;
for(int i=1;i<=n;i++)
{
if(si[i]>mid)
{
continue;
}
int da=min(li[i]+mid-si[i],(int)len);
int xiao=max(li[i]-(mid-si[i]),(int)1);
sb.push_back({xiao,da});
}
int chang=sb.size();
sort(sb.begin(),sb.end());
// if(sb.empty()) return 0;
if(sb[0].first>1)
{
return 0;
}
int mmp=sb[0].second;
for(int i=1;i<chang;i++)
{
if(sb[i].first>mmp+1)
{
return 0;
}
mmp=max(sb[i].second,mmp);
}
return mmp==len;
}
signed main()
{
cin>>n>>len;
for(int i=1;i<=n;i++)
{
cin>>li[i]>>si[i];
}
int l=1,r=2e9;
while(l<r)
{
//cout<<l<<" "<<r<<endl;
int mid=(l+r)/2;
//cout<<mid<<endl;
if(check(mid))
{
r=mid;
}else
{
l=mid+1;
}
//cout<<l<<" "<<r<<endl;
}
cout<<r;
return 0;
}