ARC120E - 1D Party-锐单电子商城

解法一

两分至少需要多少秒，设置至少需要多少秒 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<bits/stdc++.h>
#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<bits/stdc++.h>
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);
}

资讯详情

ARC120E - 1D Party

解法一

解法二

动力学技术KTU1121 USB Type-C 端口保护器的介绍、特性、及应用

ARC120E - 1D Party

解法一

解法二

动力学技术KTU1121 USB Type-C 端口保护器的介绍、特性、及应用

最近热搜

历史搜索 清除历史记录

历史搜索清除历史记录