CF1922C Closest Cities 题解

解题思路

贪心，能走距离最短的城市就一定走。

分别考虑 \(x>y\) 和 \(x<y\) 的情况，两种情况分别是从后向前转移和从前往后转移，分别预处理一个前缀和和后缀和即可。

AC 代码

#include<stdio.h>
#include<stdlib.h>
#include <valarray>
#define N 100005
#define ll long long
int n,m,a[N],clo[N];
ll sum[N],suf[N];
inline void work(){
    scanf("%d",&n);
    for(register int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    clo[1]=2,clo[n]=n-1;
    for(register int i=2;i<n;++i){
        int d1=a[i+1]-a[i];
        int d2=a[i]-a[i-1];
        clo[i]=d1<d2?i+1:i-1;
    }
    for(register int i=2;i<=n;++i)
        sum[i]=sum[i-1]+(clo[i-1]==i?1:a[i]-a[i-1]);
    for(register int i=n-1;i>=1;--i)
        suf[i]=suf[i+1]+(clo[i+1]==i?1:a[i+1]-a[i]);
    scanf("%d",&m);
    int x,y;while(m--){
        scanf("%d%d",&x,&y);
        if(x<y)
            printf("%lld\n",sum[y]-sum[x]);
        else printf("%lld\n",suf[y]-suf[x]);
    }
}
signed main(){
    int T;scanf("%d",&T);
    while(T--) work();
}