CF1976B 题解

ikunTLE · 2024-06-05 19:08:18 · 题解

题目传送门

思路

对序列 a 和序列 b 的前 n 个数，我们无法改变它们，只能累计 a_i-b_i 的绝对值。

那么我们该如何确定 b_{n+1} 所需要的代价呢？

• 如果 a_i 累加或者累减的时候恰好是 b_{n+1}，那么这个代价就是 0。

• 否则只能取与与 b_{n+1} 差值最小的值作为代价。

但是答案并不是上述所求的和，因为将 a_i 复制到 b_{n+1} 需要的代价为 1，最终答案应该再加上 1。

AC CODE

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int t,n,x,a[N],b[N];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
        long long ans=0;
        for(int i=1;i<=n;++i){
            scanf("%d",&b[i]);
            if(a[i]>b[i])//为了方便计算，我们让a[i]<=b[i]
                swap(a[i],b[i]);
            ans+=b[i]-a[i];//计算a[i]与b[i]的绝对值
        }
        scanf("%d",&x);//即b[n+1]
        int temp=0x7FFFFFFF;
        for(int i=1;i<=n;++i){
            if(a[i]<=x&&x<=b[i]){//说明b[n+1]再a[i]与b[i]之间
                temp=0;//所以代价为0
                break;
            }
            temp=min(temp,int(min(abs(a[i]-x),abs(b[i]-x))));
            //否则只能取与与b[n+1]差值最小的值作为代价
        }
        printf("%lld\n",ans+temp+1);
        //注意复制也需要大小为1的代价，所以最终答案上要+1
    }
    return 0;
}