题解
最大值最小 \(\to\) 二分可行性判断:
二分间断值 \(len\ \to\) 如果原序列 \(a_i-a_{i-1}>len\) \(\to\) 双指针判断有没有 \(b+f\) 使得 \(a_i-len<=b+f<=a_{i-1}+len\)
由于只能使用一次,所以若使用两次也算错
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100005]={0},d[200005]={0},f[200005]={0};
ll n,m,k;
inline void read(ll &x) {
x = 0;
ll flag = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') flag = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
x *= flag;
}
inline void write(ll x)
{
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
ll in(ll l,ll r)
{
ll j=k;
for(ll i=1;i<=m;i++)
{
while(j&&d[i]+f[j]>r)j--;
if(!j) return 0;
if(d[i]+f[j]>=l) return 1;
}
return 0;
}
ll check(ll maxlen)
{
ll flag=0;
for(ll i=2;i<=n;i++)
{
if(a[i]-a[i-1]>maxlen)
{
if(flag)return 0;
flag=1;
if(!in(a[i]-maxlen,a[i-1]+maxlen)) return 0;
}
}
return 1;
}
int main()
{
ll t;
read(t);
while(t--)
{
read(n); read(m); read(k);
ll l=-1,r=0;
for(ll i=1;i<=n;i++)
{
read(a[i]);
if(i>1) r=max(a[i]-a[i-1],r);
}
for(ll i=1;i<=m;i++) read(d[i]);
for(ll i=1;i<=k;i++) read(f[i]);
sort(d+1,d+m+1);
sort(f+1,f+k+1);
while(l+1<r)
{
ll mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid;
}
write(r); putchar('\n');
}
return 0;
}
···
标签:return,read,ll,mid,len,flag,Imbalance,Rudolf
From: https://www.cnblogs.com/pure4knowledge/p/18073898