ARC120E - 1D Party
时间:2023-10-09 04:07:02
解法一
两分至少需要多少秒,设置至少需要多少秒 m m m秒。
设 d p i , 0 dp_{i,0} dpi,0为第 i i i个人先往右,遇第 i 1 i 1 i 1个人之后再往左, m m m秒内第 i i i个人最多能右走多远。
设 d p i , 1 dp_{i,1} dpi,1为第 i i i个人先往左,遇第 i ? 1 i-1 i?1个人再往右, m m m秒内第 i i i个人至多能往右走多远。
初始状态为 d p 1 , 0 = d p 1 , 1 = m dp_{1,0}=dp_{1,1}=m dp1,0=dp1,1=m。
然后分析转移:
1.第 i − 1 i-1 i−1个人先往右,第 i i i个人先往左,则他们会在第 a i − a i − 1 2 \frac{a_i-a_{i-1}}{2} 2ai−ai−1秒再两个人的中点相遇,这要求 d p i − 1 , 0 ≥ a i − a i − 1 2 dp_{i-1,0}\ge \frac{a_i-a_{i-1}}{2} dpi−1,0≥2ai−ai−1才能转移,随后第 i i i个人要先跑 a i − a i − 1 2 \frac{a_i-a_{i-1}}{2} 2ai−ai−1秒回到点 a i a_i ai,再继续往右跑,有:
if(dp[i-1][0]>=(a[i]-a[i-1])/2)
dp[i][1]=max(dp[i][1],m-(a[i]-a[i-1]));
2.第 i − 1 i-1 i−1个人先往右,第 i i i个人先往右,再他们同时往右的过程中他们的距离始终为 a i − a i − 1 a_i-a_{i-1} ai−ai−1,这要求第 i − 1 i-1 i−1个人往右跑的最后 a i − a i − 1 2 \frac{a_i-a_{i-1}}{2} 2ai−ai−1秒第 i i i个人必须往左他们才能相遇,有:
if(dp[i-1][0]>=(a[i]-a[i-1])/2)
dp[i][0]=max(dp[i][0],dp[i][0]-(a[i]-a[i-1])/2);
3.第 i − 1 i-1 i−1个人先往左,第 i i i个人先往右, m m m秒后第 i − 1 i-1 i−1个人一定停留再点 a i − 1 + d p i − 1 , 1 a_{i-1}+dp_{i-1,1} ai−1+dpi−1,1,只需要保证第 i i i个人至少往左跑 a i − ( a i − 1 + d p i − 1 , 1 ) a_i-(a_{i-1}+dp_{i-1,1}) ai−(ai−1+dpi−1,1)步即可,剩下的步数都可用于往右跑一个来回 ,有:
if(m>=a[i]-a[i-1]-dp[i-1][1])
dp[i][0]=max(dp[i][0],(m-(a[i]-a[i-1]-dp[i-1][1]))/2));
4.第 i − 1 i-1 i−1个人先往左,第 i i i个人先往左,这种情况可以推测第 i − 1 i-1 i−1个人至少需要往左跑 m − d p i − 1 , 1 2 \frac{m-dp_{i-1,1}}{2} 2m−dpi−1,1步,同样在他们同时往左的过程中距离始终为 a i − a i − 1 a_i-a_{i-1} ai−ai−1,这要求第 i − 1 i-1 i−1个人往右跑的前 a i − a i − 1 2 \frac{a_i-a_{i-1}}{2} 2ai−ai−1秒第 i i i个人继续保持往左跑 i − 1 i-1 i−1和 i i i才能相遇,则第 i i i个人至少需要往左跑 m − d p i − 1 , 1 2 + a i − a i − 1 2 \frac{m-dp_{i-1,1}}{2}+\frac{a_i-a_{i-1}}{2} 2m−dpi−1,1+2ai−ai−1步,剩余步数先跑回点 a i a_i ai再继续往右,有:
if((m-dp[i-1][1])/2+(a[i]-a[i-1])/2<=m)
dp[i][1]=max(dp[i][1],m-2*((m-dp[i-1][1])/2+(a[i]-a[i-1])/2)));
时间复杂度 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))。
#include
#define inf 0x3f3f3f3f
typedef unsigned long long ull;
typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define nep(i,r,l) for(int i=r;i>=l;i--)
void sc(int &x){
scanf("%d",&x);}
void sc(int &x,int &y){
scanf("%d%d",&x,&y);}
void sc(int &x,int &y,int &z){
scanf("%d%d%d",&x,&y,&z);}
void sc(ll &x){
scanf("%lld",&x);}
void sc(ll &x,ll &y){
scanf("%lld%lld",&x,&y);}
void sc(ll &x,ll &y,ll &z){
scanf("%lld%lld%lld",&x,&y,&z);}
void sc(char *x){
scanf("%s",x);}
void sc(char *x,char *y){
scanf("%s%s",x,y);}
void sc(char *x,char *y,char *z){
scanf("%s%s%s",x,y,z);}
void out(int x){
printf("%d\n",x);}
void out(ll x){
printf("%lld\n",x);}
void out(int x,int y){
printf("%d %d\n",x,y);}
void out(ll x,ll y){
printf("%lld %lld\n",x,y);}
void out(int x,int y,int z){
printf("%d %d %d\n",x,y,z);}
void out(ll x,ll y,ll z){
printf("%lld %lld %lld\n",x,y,z);}
using namespace std;
#define inf 0x3f3f3f3f
const int N=3e5+5;
int n,a[N];
int dp[N][2];
void update(int &x,int y)
{
x=max(x,y);
}
bool judge(int m)
{
memset(dp,-inf,sizeof(dp));
dp[1][0]=dp[1][1]=m;
for(int i=2;i<=n;i++)
{
bool flag=false;
if(dp[i-1][0]>=(a[i]-a[i-1])/2)
{
update(dp[i][1],m-(a[i]-a[i-1]));
update(dp[i][0],dp[i-1][0]-(a[i]-a[i-1])/2);
flag=true;
}
if(m>=a[i]-a[i-1]-dp[i-1][1])
{
update(dp[i][0],(m-(a[i]-a[i-1]-dp[i-1][1]))/2);
flag=true;
}
if((m-dp[i-1][1])/2+(a[i]-a[i-1])/2<=m)
{
update(dp[i][1],m-2*((m-dp[i-1][1])/2+(a[i]-a[i-1])/2));
flag=true;
}
if(!flag) return false;
}
return true;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
sc(n);
rep(i,1,n) sc(a[i]);
int l=0,r=(a[n]-a[1])/2,ans;
while(l<=r)
{
int m=l+r>>1;
if(judge(m)) ans=m,r=m-1;
else l=m+1;
}
out(ans);
}
解法二
用 s i = L s_i=L si=L表示第 i i i个人先往左,碰到第 i − 1 i-1 i−1个人之后再往右。
用 s i = R s_i=R si=R表示第 i i i个人先往右,碰到第 i + 1 i+1 i+1个人之后再往左。
特别的,有 s 1 = R , s n = L s_1=R,s_n=L s1=R,sn=L。
将 s 1 s 2 . . . s n s_1s_2...s_n s1s2...sn按如下方式分段:
R . . . R L . . . L , R . . . R L . . . L , . . . . R...RL...L,R...RL...L,.... R...RL...L,R...RL...L,....
设 s a . . . s b s c . . . s d = R . . . R L . . . L s_a...s_bs_c...s_d=R...RL...L sa...sbsc...sd=R...RL...L,则对于 i ∈ [ a , d ) i\in[a,d) i∈[a,d)满足 i i i和 i + 1 i+1 i+1至少相遇一次的时间为 F ( a , b , c , d ) = A c − A b 2 + m a x ( A b − A a 2 , A d − A c 2 ) = m a x ( A c − A a , A d − A b ) 2 F(a,b,c,d)=\frac{A_c-A_b}{2}+max(\frac{A_b-A_a}{2},\frac{A_d-A_c}{2})\\=\frac{max(A_c-A_a,A_d-A_b)}{2} F(a,b,c,d)=2Ac−Ab+max(2Ab−Aa,2Ad−Ac)=2max(Ac−Aa,Ad−Ab)
对于 s a . . . s b s c . . . s d = R . . . R L . . . L s_a...s_bs_c...s_d=R...RL...L sa...sbsc...sd=R...RL...L和 s e . . . s f s g . . . s h = R . . . R L . . . L ( e = d + 1 ) s_e...s_fs_g...s_h=R...RL...L(e=d+1) se...sfsg...sh=R...RL...L(e=d+1),对于 i ∈ [ a , h ) i\in[a,h) i∈[a,h)满足 i i i和 i + 1 i+1 i+1都碰撞一次的时间为 m a x ( F ( a , b , c , d ) , F ( e , f , g , h ) , A g − A b 2 ) max(F(a,b,c,d),F(e,f,g,h),\frac{A_g-A_b}{2}) max(F(a,b,c,d),F(e,f,g,h),2Ag−Ab)( d , e d,e d,e碰撞的时间为 A g − A b 2 \frac{A_g-A_b}{2} 2Ag−Ab)
于是可以设 d p d , b dp_{d,b} dpd,b为第 1... d 1...d 1...d的位置划分好后,上一个 R R R出现的位置为 b b b,对于 i ∈ [ 1 , d ) i\in[1,d) i∈[1,d)满足 i i i和 i + 1 i+1 i+1都碰撞一次所需要的最小时间。
有转移
d p h , f = m i n { d p h , f , m a x ( d p d , b , A f + 1 − A b 2 , F ( d + 1 , f , f + 1 , h ) ) } dp_{h,f}=min\{dp_{h,f},max(dp_{d,b},\frac{A_{f+1}-A_b}{2},F(d+1,f,f+1,h))\} dph,f=min{
dph,f,max(dpd,b,2Af+1−Ab,F(d+1,f,f+1,h))}
可以得到 O ( n 4 ) O(n^4) O(n4)的 d p dp dp。
现在证明最优的情况不会出现 s i − 1 s i s i + 1 s i + 2 = R L L L 、 R R R L 、 R L R L s_{i-1}s_is_{i+1}s_{i+2}=RLLL、RRRL、RLRL si−1sisi+1si+2=RLLL、RRRL、RLRL的情况(结论1):
若 s i − 1 s i s i + 1 s i + 2 = R L L L s_{i-1}s_is_{i+1}s_{i+2}=RLLL si−1sisi+1si+2=RLLL,则 ( i − 1 , i ) , ( i , i + 1 ) , ( i + 1 , i + 2 ) (i-1,i),(i,i+1),(i+1,i+2) (i−1,i),(i,i+1),(i+1,i+2)都碰撞一次所花费的时间为 A i + 2 − A i − 1 2 \frac{A_{i+2}-A_{i-1}}{2} 2Ai+2−Ai−1,第 i + 1 i+1 i+1个人和第 i + 2 i+2 i+2个人会在点 A i − 1 + A i + 2 2 \frac{A_{i-1}+A_{i+2}}{2} 2Ai−1+Ai+2碰撞。
若 s i − 1 s i s i + 1 s i + 2 = R R R L s_{i-1}s_is_{i+1}s_{i+2}=RRRL si−1sisi+1si+2=RRRL, ( i − 1 , i ) , ( i , i + 1 ) , ( i + 1 , i + 2 ) (i-1,i),(i,i+1),(i+1,i+2) (i−1,i),(i,i+1),(i+1,i+2)都碰撞一次花费的时间也为 A i + 2 − A i − 1 2 \frac{A_{i+2}-A_{i-1}}{2} 2Ai+2−Ai−1,第 i − 1 i-1 i−1个人和第 i i i个人会在点 A i − 1 + A i + 2 2 \frac{A_{i-1}+A_{i+2}}{2} 2Ai−1+Ai+2碰撞。
若 s i − 1 s i s i + 1 s i + 2 = R L R L s_{i-1}s_is_{i+1}s_{i+2}=RLRL si−1sisi+1si+2=RLRL, ( i − 1 , i ) , ( i , i + 1 ) , ( i + 1 , i + 2 ) (i-1,i),(i,i+1),(i+1,i+2) (i−1,i),(i,i+1),(i+1,i+2)都碰撞一次花费的时间也为 A i + 2 − A i − 1 2 \frac{A_{i+2}-A_{i-1}}{2} 2Ai+2−Ai−1,第 i i i个人和第 i + 1 i+1 i+1个人会在点 A i − 1 + A i + 2 2 \frac{A_{i-1}+A_{i+2}}{2} 2Ai−1+Ai+2碰撞。
若将上述情况改为 s i − 1 s i s i + 1 s i + 2 = R R L L s_{i-1}s_is_{i+1}s_{i+2}=RRLL si−1sisi+1si+2=RRLL,此时 ( i − 1 , i ) , ( i , i + 1 ) , ( i + 1 , i + 2 ) (i-1,i),(i,i+1),(i+1,i+2) (i−1,i),(i,i+1),(i+1,i+2)都碰撞一次的时间花费比上述两种情况都要更优, i i i和 i + 1 i+1 i+1碰撞后,由于 i − 1 , i i-1,i i−1,i都在向右运行, i + 1 , i + 2 i+1,i+2 i+1,i+2都在向左运行,故在 i , i + 1 i,i+1 i,i+1没改变方向时 i − 1 , i i-1,i i−1,i的距离始终为 A i − A i − 1 A_i-A_{i-1} Ai−Ai−1, i + 1 , i + 2 i+1,i+2 i+1,i+2保持的距离始终为 A i + 2 − A i + 1 A_{i+2}-A_{i+1} Ai+2−Ai+1,故时间花费为:
A i + 1 − A i 2 + m a x ( A i + 2 − A i + 1 2 , A i − A i − 1 2 ) = m a x ( A i + 2 − A i , A i + 1 − A i − 1 ) 2 ≤ A i + 2 − A i − 1 2 \frac{A_{i+1}-A_{i}}{2}+max(\frac{A_{i+2}-A_{i+1}}{2},\frac{A_{i}-A_{i-1}}{2}) \\=\frac{max(A_{i+2}-A_{i},A_{i+1}-A_{i-1})}{2}\le \frac{A_{i+2}-A_{i-1}}{2} 2Ai+1−Ai+max(2Ai+2−Ai+1,2Ai−Ai−1)=2max(Ai+2−Ai,Ai+1−Ai−1)≤2Ai+2−Ai−1
由结论1和 s 1 = R , s n = L s_1=R,s_n=L s1=R,sn=L,则最优情况下不会出现连续三个状态相等的情况。
于是对于 d p d , b dp_{d,b} dpd,b, b b b要么等于 d − 1 d-1 d−1,要么等于 d − 2 d-2 d−2,可以分别设为 d p d , 0 / 1 dp_{d,0/1} dpd,0/1。
上述方程就被优化到了 O ( n ) O(n) O(n)。
#include
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define nep(i,r,l) for(int i=r;i>=l;i--)
void sc(int &x){
scanf("%d",&x);}
void sc(int &x,int &y){
scanf("%d%d",&x,&y);}
void sc(int &x,int &y,int &z){
scanf("%d%d%d",&x,&y,&z);}
void sc(ll &x){
scanf("%lld",&x);}
void sc(ll &x,ll &y){
scanf("%lld%lld",&x,&y);}
void sc(ll &x,ll &y,ll &z){
scanf("%lld%lld%lld",&x,&y,&z);}
void sc(char *x){
scanf("%s",x);}
void sc(char *x,char *y){
scanf("%s%s",x,y);}
void sc(char *x,char *y,char *z){
scanf("%s%s%s",x,y,z);}
void out(int x){
printf("%d\n",x);}
void out(ll x){
printf("%lld\n",x);}
void out(int x,int y){
printf("%d %d\n",x,y);}
void out(ll x,ll y){
printf("%lld %lld\n",x,y);}
void out(int x,int y,int z){
printf("%d %d %d\n",x,y,z);}
void out(ll x,ll y,ll z){
printf("%lld %lld %lld\n",x,y,z);}
using namespace std;
const int N=3e5+5;
int n,A[N],dp[N][2];
int F(int a,int b,int c,int d)
{
return max(A[c]-A[a],A[d]-A[b]);
}
int main()
{
sc(n);
rep(i,1,n) sc(A[i]);
memset(dp,inf,sizeof(dp));
dp[1][0]=0;
dp[2][0]=dp[2][1]=A[2]-A[1];
A[0]=A[1];A[n+1]=A[n];
//特别第A[1]可以看成一个LR
//A[n]可以看成一个LR 因此把序列两边扩展一下
for(int i=1;i<=n+1;i++)
for(int j=0;j<=1;j++)
if(dp[i][j]!=inf)
{
int b=i-1-j;
for(int f=i+1;f<=i+2&&f<=n;f++)
for(int h=f+1;h<=f+2&&h<=n+1;h++)
dp[h][f==h-2]=min(dp[h][f==h-2],max(dp[i][j],max(A[f+1]-A[b],F(i+1,f,f+1,h))));
}
out(min(dp[n+1][0],dp[n+1][1])/2);
}