关键观察

• 设连续三元组为 $(x,\,y,\,z)$。若删除中间元素 $y$，新的贡献变为 $|x-z|$。 要想权值不变，必须满足

  $$|x-y|+|y-z|=|x-z|.$$

• 上式等价于

  $$(x\le y\le z)\quad\text{或}\quad(x\ge y\ge z),$$

  即 $y$ 处于 $[x,z]$ 区间内部——三点单调（含相等）时，中间点可安全删除。

因此，只需留下：

1. 整体最左、最右端点；
2. 所有“拐点”（峰值或谷值）。

其余都能删掉。

算法

判断可删条件

对当前栈顶两个元素 $s_{k-1},s_k$ 和读入的新元素 $v$： 若

$(s_{k-1}\le s_k\le v)$或$(s_{k-1}\ge$ $s_k\ge v)$,

则 $s_k$ 可删；弹栈并继续判断，直到条件不满足或栈不足 2 个。

复杂度

• 时间：每个元素至多入栈、出栈一次，$O(n)$
• 空间：栈 $O(n)$（最坏单调波形全保留）

参考代码

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    long long x;  cin >> x;          // a1
    long long p2 = 0, p1 = x;        // p2 无效用 0 占位
    int keep = 1;                    // 已保留数量

    for (int i = 2; i <= n; ++i) {
        long long v; cin >> v;
        if (v == p1) continue;       // 相邻相等可删

        if (keep >= 2 && ((p2 <= p1 && p1 <= v) || (p2 >= p1 && p1 >= v))) {
            // 删除 p1，用 v 覆盖
            p1 = v;
        } else {
            // v 是拐点，需保留
            p2 = p1;
            p1 = v;
            ++keep;
        }
    }
    cout << n - keep << '\n';
    return 0;
}

Java

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long first = Long.parseLong(st.nextToken());   // a1
        long p2 = 0, p1 = first;                       // p2 暂无效
        int keep = 1;

        for (int i = 2; i <= n; i++) {
            long v = Long.parseLong(st.nextToken());
            if (v == p1) continue;                     // 相邻相等

            if (keep >= 2 && ((p2 <= p1 && p1 <= v) || (p2 >= p1 && p1 >= v))) {
                p1 = v;                               // 删 p1
            } else {
                p2 = p1;
                p1 = v;
                keep++;
            }
        }
        System.out.println(n - keep);
    }
}

Python

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

first = a[0]
p2 = None          # 倒数第二个保留点
p1 = first         # 最新保留点
keep = 1           # 已保留数量

for v in a[1:]:
    if v == p1:
        continue   # 相邻相等可删
    if p2 is not None and ((p2 <= p1 <= v) or (p2 >= p1 >= v)):
        p1 = v     # 删除 p1
    else:
        p2, p1 = p1, v
        keep += 1

print(n - keep)

题目内容

小A有一个长度为 $n$ 的数组 $a_1,a_2,...,a_n$ 。

定义数组的权值为 $|a_1-a_2,|+|a_2-a_3|...+|a_{n-1}-a_n|$，长度为 $1$ 的数组权值为 $0$ 。

现在小A想玩一个删数字的游戏，他想在数组中删去若干个数(不能全部删完)，并保证剩下数组的权值不变。

小A想知道在采取最优策略的情况下，他最多可以删掉多少个数字，你可以告诉他吗?

输入描述

第一行一个正整数 $n$ ，表示数字个数。

第二行 $n$ 个正整数，表示 $a_i$ 。

$1≤n≤10^5,1≤a_i≤10^9$

输出描述

输出一行，一个正整数，表示最多可以删去几个数。

样例1

输入

10
1 2 8 8 9 1 1 1 5 5

输出

6

样例2

输入

5
6 6 6 6 6

输出

4