Codeforces Round #688 (Div. 2) 1453 B

89 阅读 0 评论 59 点赞

我是靠谱客的博主年轻舞蹈，最近开发中收集的这篇文章主要介绍Codeforces Round #688 (Div. 2) 1453 B，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

原题链接

Gildong has an interesting machine that has an array a with n integers. The machine supports two kinds of operations:

Increase all elements of a suffix of the array by 1.
Decrease all elements of a suffix of the array by 1.
A suffix is a subsegment (contiguous elements) of the array that contains an. In other words, for all i where ai is included in the subsegment, all aj’s where i<j≤n must also be included in the subsegment.

Gildong wants to make all elements of a equal — he will always do so using the minimum number of operations necessary. To make his life even easier, before Gildong starts using the machine, you have the option of changing one of the integers in the array to any other integer. You are allowed to leave the array unchanged. You want to minimize the number of operations Gildong performs. With your help, what is the minimum number of operations Gildong will perform?

Note that even if you change one of the integers in the array, you should not count that as one of the operations because Gildong did not perform it.

Input
Each test contains one or more test cases. The first line contains the number of test cases t (1≤t≤1000).

Each test case contains two lines. The first line of each test case consists of an integer n (2≤n≤2⋅105) — the number of elements of the array a.

The second line of each test case contains n integers. The i-th integer is ai (−5⋅108≤ai≤5⋅108).

It is guaranteed that the sum of n in all test cases does not exceed 2⋅105.

Output
For each test case, print one integer — the minimum number of operations Gildong has to perform in order to make all elements of the array equal.

Example
inputCopy
7
2
1 1
3
-1 0 2
4
99 96 97 95
4
-3 -5 -2 1
6
1 4 3 2 4 1
5
5 0 0 0 5
9
-367741579 319422997 -415264583 -125558838 -300860379 420848004 294512916 -383235489 425814447
outputCopy
0
1
3
4
6
5
2847372102
Note
In the first case, all elements of the array are already equal. Therefore, we do not change any integer and Gildong will perform zero operations.

In the second case, we can set a3 to be 0, so that the array becomes [−1,0,0]. Now Gildong can use the 2-nd operation once on the suffix starting at a2, which means a2 and a3 are decreased by 1, making all elements of the array −1.

In the third case, we can set a1 to 96, so that the array becomes [96,96,97,95]. Now Gildong needs to:

Use the 2-nd operation on the suffix starting at a3 once, making the array [96,96,96,94].
Use the 1-st operation on the suffix starting at a4 2 times, making the array [96,96,96,96].
In the fourth case, we can change the array into [−3,−3,−2,1]. Now Gildong needs to:

Use the 2-nd operation on the suffix starting at a4 3 times, making the array [−3,−3,−2,−2].
Use the 2-nd operation on the suffix starting at a3 once, making the array [−3,−3,−3,−3].

题意

给定t组样例，给定一个n表示数组的长度，然后输入数组

操作：先去掉数组中的一个数，然后进行+1/-1的操作（只能从后往前操作），比如可以给数组最后i（i<=n）个连续的值+1/-1，问最少需要操作多少次，使得数组中的值相同

思路

看大神思路
首先观察通过后缀来改变数组，会有什么性质。
首先，若先不考虑把一个数换掉，要想把所有数变得相等，因为最优肯定是变成最大最小值之间的一个数（不然还要多花步数），所以要花的次数肯定是数组的差分和。
现在我们改变一个数的效果是什么？我们看一下三个例子

7 5 3 （从后往前递增）
把5改成【3,7】之间的都是最优的

3 5 7 （从后往前递减）
同上

7 3 5 （中间“断崖”）

显然5会经历先变成3再一起变成7的过程，这里就浪费了掉到3的步数，这个时候把3换成【5,7】之间的数就同上了。
所以换数产生更优方法的地方就在于消除“断崖”。而这个过程又相当于“去掉了”这个数。
所以我们再处理完差分和的时候，遍历一遍去掉哪个数最优即可~

AC代码

package Codeforces.div2_688_1453;

import java.util.Scanner;

public class B {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            long[] a = new long[n + 5];
            for (int i = 1; i <= n; i++) {
                a[i] = sc.nextInt();
            }
            long[] d = new long[n + 5];
            long sum = 0;
            for (int i = 1; i <= n; i++) {
                d[i] = a[i] - a[i - 1];
                if (i > 1) {
                    sum += Math.abs(d[i]);
                }
            }
            long maxn = 0;
            for (int i = 1; i <= n; i++) {
                long x = Math.abs(d[i]);
                long y = Math.abs(d[i + 1]);
                if (i == 1) {
                    maxn = Math.max(maxn, Math.abs(d[i + 1]));
                } else if (i == n)
                    maxn = Math.max(maxn, Math.abs(d[n]));
                else {
                    maxn=Math.max(maxn,x+y-Math.abs(d[i]+d[i+1]));
                }
            }
            System.out.println(sum - maxn);
        }
    }
}