For an array of integers [a1,a2,…,an], let's call the value |a1−a2|+|a2−a3|+⋯+|an−1−an| 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≤t≤104 ) — the number of test cases. The first line of each test case contains a single integer n (1≤n≤3⋅105) — the size of the array a . The second line contains n integers a1,a2,⋅,an (0≤ai≤109 ) — elements of the array itself. The sum of n over all test cases doesn't exceed 3⋅105.
时间: 2023-06-18 11:04:41 浏览: 68
题意简述:
给定一个长度为 $n$ 的整数数组 $a$,求该数组的一个非空子序列 $b$,使得 $b$ 的对比度与 $a$ 的对比度相等。对比度的定义为 $|a_1 - a_2| + |a_2 - a_3| + \cdots + |a_{n-1} - a_n|$。
解题思路:
根据对比度的定义,我们可以得到:
$|a_1 - a_2| + |a_2 - a_3| + \cdots + |a_{n-1} - a_n| = |a_1 - a_n| + |a_n - a_{n-1}| + \cdots + |a_2 - a_1|$
我们可以令 $b$ 为 $a$ 中某个值最大/最小的数,然后在 $a$ 中寻找与 $b$ 相邻的两个数,即 $a_i$ 和 $a_j$,满足 $a_i < b < a_j$ 或 $a_i > b > a_j$,然后将这个区间的数取出来组成子序列 $b$ 即可。
为什么这样做是正确的呢?因为对于一个区间 $[a_i, a_j]$,我们可以将 $b$ 看作是左右两个端点中较大/较小的那个,那么我们只需要考虑 $a_i$ 和 $a_j$ 与 $b$ 的关系即可。
时间复杂度为 $O(n)$。
参考代码:
相关问题
请给出下题的c++参考代码For an array of integers [a1,a2,…,an], let's call the value |a1−a2|+|a2−a3|+⋯+|an−1−an| 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≤t≤104 ) — the number of test cases. The first line of each test case contains a single integer n (1≤n≤3⋅105) — the size of the array a . The second line contains n integers a1,a2,⋅,an (0≤ai≤109 ) — elements of the array itself. The sum of n over all test cases doesn't exceed 3⋅105 . Output For each test case, print a single integer — the minimum possible size of the array b .
以下是参考代码,时间复杂度为O(n):
```c++
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int a[n];
long long sum = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (i > 0) {
sum += abs(a[i] - a[i - 1]);
}
}
long long max_diff = 0;
for (int i = 1; i < n - 1; i++) {
max_diff = max(max_diff, abs(a[i] - a[i - 1]) + abs(a[i + 1] - a[i]) - abs(a[i + 1] - a[i - 1]));
}
cout << sum - max_diff << endl;
}
return 0;
}
```
思路:
题目要求找到一个非空子序列,其 contrast 值等于原序列的 contrast 值,且该子序列长度最小。对于一个长度大于等于2的子序列,其 contrast 值可以拆分成相邻元素之差的绝对值之和,即
|a[i]-a[i-1]| + |a[i+1]-a[i]|
利用绝对值的性质,可以将其拆分为
(a[i]-a[i-1]) + (a[i+1]-a[i]), a[i]>a[i-1] and a[i+1]>a[i]
(a[i-1]-a[i]) + (a[i]-a[i+1]), a[i]<a[i-1] and a[i+1]<a[i]
(a[i]-a[i-1]) + (a[i]-a[i+1]), a[i]>a[i-1] and a[i+1]<a[i]
(a[i-1]-a[i]) + (a[i+1]-a[i]), a[i]<a[i-1] and a[i+1]>a[i]
其中第三种情况需要特殊处理,即对于一个数列 a,找到一个位置 i,使得 a[i-1]<a[i]>a[i+1],将 a[i] 从子序列中删除,即可得到一个新的子序列,其 contrast 值等于原序列的 contrast 值。
因此,我们可以遍历整个序列,计算出原序列的 contrast 值。然后再遍历一遍序列,找到最大的相邻元素之差,计算出其对应的拆分方式,即可得到最小的子序列长度。
C语言给定 n 个整数 a1, a2, … , an ,求它们两两相乘再相加的和,即 S = a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an-2 · an-1 + an-2 · an + an-1 · an.
这个问题可以用双重循环来解决,第一个循环变量 i 从 0 到 n-2,第二个循环变量 j 从 i+1 到 n-1。在循环中,每次将 ai 和 aj 相乘,然后加到 sum 变量中。最后得到的 sum 就是所求的结果。
以下是 C 语言代码实现:
```c
#include <stdio.h>
int main() {
int n, i, j, sum = 0;
printf("Enter the number of integers: ");
scanf("%d", &n);
int a[n];
printf("Enter %d integers: ", n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (i = 0; i < n-1; i++) {
for (j = i+1; j < n; j++) {
sum += a[i] * a[j];
}
}
printf("The sum of pairwise multiplication is %d\n", sum);
return 0;
}
```
输入样例:
```
Enter the number of integers: 5
Enter 5 integers: 1 2 3 4 5
```
输出样例:
```
The sum of pairwise multiplication is 35
```