题解：CF1922C（Closest Cities）

题解：CF1922C（Closest Cities）

• 题意简述

给扔俩链接……

Problem - C - Codeforces。

Closest Cities - 洛谷。

• 思路解析

第一步，我们要证明，无论怎么走，最终的路线都是一条直线。这里我们用反证法,并以从左往右走为例（从右往左同理）。

首先，我们从x城市走到y号城市（花费a[y]-a[x]）可以拆分成无数次走到相邻城市的步骤（注意花费不一定是1），因为这样走总的花费=(a[x+1]-a[x]或1)+(a[x+2]-a[x+1]或1)+...+(a[y]-a[y-1]或1)≤(a[x+1]-a[x])+(a[x+2]-a[x+1])+...+(a[y]-a[y-1])≤a[y]-a[x]（因为相邻的两个a不相等，所以他们的差大于等于1）。所以最终的总路线可以理解成每一步都是在相邻的城市之间走。

若要使得路线不是直线，我们一定会在某一个城市（记作x）向相反的方向走，到最后一定会折反回来，必然途径x，那么由x到前面再回到x的这部分就可不走，因此路线不为直线一定不是最优。

第二步，根据结论设计算法。因为走的路程都是单向的，所以最终的路线只有两种情况：从左往右和从右往左。我们维护两个数组，一个dis1[i]表示从1走到i的花费，一个disn[i]表示从n走到i的花费。

那么从x走到y，若x<y，其代价为dis1[y]-dis1[x]；若x>y，其代价为disn[y]-disn[x]，原理很简单，概不详述。

第三步，我们要确定如何求两个数组。初始化，dis1[1]=0、disn[n]=0。

这有点类似于动态规划。如果a[i-1]离a[i]最近，dis1[i]=dis1[i-1]+1，否则dis1[i]=dis1[i-1]+(a[i]-a[i-1])。如果a[i+1]离a[i]最近，disn[i]=disn[i+1]+1，否则disn[i]=disn[i+1]+(a[i]-a[i+1])。

问题就这样轻松的解决啦！

• 代码示范

如果我说的不明白，码上给大家解决。

#include<bits/stdc++.h>
#define N 110000
using namespace std;
int a[N]={},dis1[N]={},disn[N]={},m=0,n=0,t=0;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        a[0]=-(1<<30);
        a[n+1]=(1<<30)+1e9;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        dis1[1]=0;
        for(int i=2;i<=n;i++){
            if(a[i]-a[i-1]<=a[i-1]-a[i-2]){
                dis1[i]=dis1[i-1]+1;
            }else{
                dis1[i]=dis1[i-1]+(a[i]-a[i-1]);
            }
        }
        disn[n]=0;
        for(int i=n-1;i>=1;i--){
            if(a[i+1]-a[i]<=a[i+2]-a[i+1]){
                disn[i]=disn[i+1]+1;
            }else{
                disn[i]=disn[i+1]+(a[i+1]-a[i]);
            }
        }
        scanf("%d",&m);
        for(int i=1;i<=m;i++){
            int x=0,y=0;
            scanf("%d%d",&x,&y);
            if(x==y){
                printf("0\n");
            }else{
                if(x<y){
                    printf("%d\n",dis1[y]-dis1[x]);
                }else{
                    printf("%d\n",disn[y]-disn[x]);
                }
            }
        }
    }
    return 0;
}

• 坑点排查

在设计最大值的时候，一定要注意，减掉某个数之后它还是不是最大值。