CF1832C Contrast Value

Zinc-Acetate / 2024-01-26 / 原文

题目传送门

codeforces

洛谷

题面

For an array of integers $[a_1, a_2, \dots, a_n]$, let's call the value $|a_1-a_2|+|a_2-a_3|+\cdots+|a_{n-1}-a_n|$ the contrast of the array. Note that the contrast of an array of size $1$ is equal to $0$.

You are given an array of integers $a$. Your task is to build an array of $b$ in such a way that all the following conditions are met:

$b$ is not empty, i.e there is at least one element;
$b$ is a subsequence of $a$, i.e $b$ can be produced by deleting some elements from $a$ (maybe zero);
the contrast of $b$ is equal to the contrast of $a$.

What is the minimum possible size of the array $b$?

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the size of the array $a$.

The second line contains $n$ integers $a_1, a_2, \cdot, a_n$ ($0 \le a_i \le 10^9$) — elements of the array itself.

The sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$.

Output

For each test case, print a single integer — the minimum possible size of the array $b$.

题目大意

对于一个由整数 $[a_1, a_2, \dots, a_n]$ 组成的数组，我们把数值 $|a_1-a_2|+|a_2-a_3|+\cdots+|a_{n-1}-a_n|$ 称为数组的对比度。大小为 $1$ 的数组的对比度等于 $0$ 。

给你一个整数数组 $a$ 。你的任务是以满足以下所有条件的方式建立一个 $b$ 数组：

$b$ 不是空数组。
$b$ 是 $a$ 的子序列。
$b$ 的对比度等于 $a$ 的对比度。

数组 $b$ 的最小可能长度是多少？

思路

观察 $|a_1-a_2|+|a_2-a_3|+\cdots+|a_{n-1}-a_n|$ ，我们发现如果可以把绝对值去掉，这玩意就会变成 $a_1-a_n$ 。所以容易想到：

如果区间 $[l, r]$ 单调递增，这一区间所贡献的对比度 $|a_l-a_{l+1}|+|a_{l+1}-a_{l+2}|+\cdots+|a_{r-1}-a_r|=a_{l+1}-a_l+a_{l+2}-a_{l+1}+\cdots+a_r-a_{r-1}=a_r-a_l$ ；
如果区间 $[l, r]$ 单调递减，这一区间所贡献的对比度 $|a_l-a_{l+1}|+|a_{l+1}-a_{l+2}|+\cdots+|a_{r-1}-a_r|=a_l-a_{l+1}+a_{l+1}-a_{l+2}+\cdots+a_{r-1}-a_r=a_l-a_r$ 。

也就是说，当区间 $[l, r]$ 单调时，这一区间所贡献的对比度只和首尾的 $a_l$ 和 $a_r$ 有关，中间的数去掉不影响这段区间所贡献的对比度，所以要想找到最短的满足要求的子序列，就是要把数组 $a$ 中这些不影响区间所贡献的对比度的数都去掉，只留下两端的 $a_l$ 和 $a_r$ ，所以留下的元素的数量就等于这个数组的单调区间的个数 $+1$ 。

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve()
{
    int n, b = 0, ans = 1;
    cin >> n;
    vector<int> a(n);
    cin >> a[0];
    for (int i = 1; i < n; i++)
    {
        cin >> a[i];
        if (a[i] > a[i - 1] && b != 1)
        {
            ans++;
            b = 1;
        }
        if (a[i] < a[i - 1] && b != 2)
        {
            ans++;
            b = 2;
        }
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}