杭电多校十 - Wavy Tree (贪心)

http://acm.hdu.edu.cn/contest/problem?cid=1053&pid=1003

---

题意
给定一个长度为 n 的数列，每次操作可以使得其中的某个元素 +1 或 -1。
问，最少经过多少次操作能满足：

• 对于任意 $1<i<n$ 都有 a i > max ⁡ { a i − 1 , a i + 1 } a_i > \max \{a_{i-1},a_{i+1}\} ai​>max{ai−1​,ai+1​} 或 a i < min ⁡ { a i − 1 , a i + 1 } a_i < \min \{a_{i-1},a_{i+1}\} ai​<min{ai−1​,ai+1​} 成立。

$1\le n\le 10^6,1\le b_i\le 10^9$

思路
场上想这道题的时候思维都是混乱的，一直想着怎么变才能让这个位置都大于两边的数或者都小于两边的数，然后这个数变过之后又会对后面的数产生影响，然后就不知道怎么变了。。

其实应该想想最后的数列变成了什么样，每个位置都比两边大或者比两边小，那么最终的数列就呈波浪形，然后只有两种模型。一种是偶数位置都比奇数位置大，一种是偶数位置都比奇数位置小。
就这两种情况，取这两种情况中的最小值就行了。

所以先确定一种情况，求出得到这种模型的最小操作数。然后就是贪心求解。
如果当前位置很小，而要变成比左右两个位置都大，那么此时不应该将当前位置 i 直接变成左右最大值+1，而是把当前位置 i 变成左边位置(i-1) +1，然后把右边位置(i+1) 变成当前位置 -1。容易发现这两种方式的操作次数是一样的，但是后者更能使答案更优。
因为此时 右边的位置(i+1) 是要变成偏低的位置，而 其右边的位置(i+2) 要变成偏高的位置，如果此时把 i+1 位置变低了，那么就是相当于给 i+2 位置更多生存的空间了，很可能其就不用操作就能满足比左右两边都大，所以就相当于节省了操作次数，这样就很贪心。

所以对每种模型，对于每个位置，只需要和上一位置比看是否满足，如果不满足就用最小操作次数调整到恰好满足。

Code

#include
using namespace std;

const int N = 2000010, mod = 1e9+7;
int T, n, m;
int a[N], b[N];

signed main(){
	scanf("%lld", &T);
	while(T--)
	{
		scanf("%lld", &n);
		for(int i=1;i<=n;i++) scanf("%lld", &a[i]);
		
		int ans = 1e18;
		int sum = 0;
		
		b[1] = a[1];
		for(int i=2;i<=n;i++)
		{
			b[i] = a[i];
			if(i % 2){
				if(b[i] >= b[i-1]) sum += b[i] - b[i-1] + 1, b[i] = b[i-1] - 1;	
			}
			else
				if(b[i] <= b[i-1]) sum += b[i-1] - b[i] + 1, b[i] = b[i-1] + 1;
		}
		ans = min(ans, sum);
		
		sum = 0;
		for(int i=2;i<=n;i++)
		{
			b[i] = a[i];
			if(i % 2 == 0){
				if(b[i] >= b[i-1]) sum += b[i] - b[i-1] + 1, b[i] = b[i-1] - 1;
			}
			else
				if(b[i] <= b[i-1]) sum += b[i-1] - b[i] + 1, b[i] = b[i-1] + 1;
		}
		ans = min(ans, sum);
		
		printf("%lld\n", ans);
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46