ZJOI2020 序列 [* hard]
给定长度为 (n) 的序列，你可以：
- 选择一个区间 ([l,r])，给区间所有数减 (1)
- 选择一个区间 ([l,r])，给区间所有奇数下标的值减 (1)
- 选择一个区间 ([l,r])，给区间所有偶数下标的值减 (1)
求最小操作次数，使得所有数变成 (0)
(nle 10^6,Tle 10,a_ile 10^9)
Solution
神仙贪心题，大概是欣赏的咕咕第一篇题解。
定义操作 (1) 为直线操作，即将 (a_{l},a_{l+1}...a_r) 集体减 (1)
定义操作 (2) 为跳线操作，即将 (a_{l},a_{l+2}...) 集体减 (1)
可以注意到一个强有力的性质：
- 假设当前有 (a_1,a_2>0)，那么至少有 (1) 次操作是从 (a_1) 处开始的直线。
考虑反证，如果没有，那么只有这样的情况：
- 操作是 (a_1) 跳线，(a_2) 直线。
显然等价于 (a_1) 直线，(a_3) 跳线（多的再直线）。
- 操作是 (a_1) 跳线，(a_2) 跳线。
显然不会优于，先 (a_1) 直线若干次，再 (a_1/a_2) 跳线。
这里的具体论证略为复杂，感性理解就好（
于是得到了一个贪心，对于 (a_1) 而言，操作 (t=min(a_1,a_2)) 次直线，剩下的都直接跳线。
但是这样难以拓展到所有数的情况。
于是维护 (A,B,C) 表示可以免费从 (a_i) 出发的直线数为 (A)，跳线数为 (B)，从 (i+1) 出发的跳线数为 (C)
这样我们可以直接对 (a_i) 进行处理。
考虑如何拓展到 (a_{i+1})
假设 (A+Cle a_{i+1})，那么我们是可以直接交换 (B,C) 并往后处理的。
假设 (A+C>a_{i+1})，那么我们相当于需要确定一个最优的 (x,y) 使得 (x+y=a_{i+1},xle A,yle C) 使得其可以方便的继续操作（因为多余的将无法衍生出去）。
设 (K=A+C-a_{i+1})，即我们多余的操作次数，那么我们会发现至少有 (A-K) 次直线和 (C-K) 条跳线是一定会执行的。
注意到 (A+C-K=(A-K)+(C-K)+K=a_{i+1})，所以我们还需要执行 (K) 次操作，这 (K) 次操作由之前的 (A) 和 (C) 提供，同时是免费的，换而言之我们希望这 (K) 次操作由 (i+1) 和 (i+2)（即往后的讨论）来帮我们解决此问题。
于是我们将答案减去 (K)，将 (A) 和 (C) 均减去 (K) 然后继续处理即可。
然而一个矛盾的点是，(A) 和 (C) 不能为负数。
没关系，假设 (A<K)，那么我们会发现有 (C) 类操作一定有 (K-A) 次没有用在 (i+1) 处（即假设多余操作均为 (A) 类，那么额外多余的操作一定还有 (K-A) 次）。
这样的话可以将 (C) 减去 (K-A)，此时的 (K'=A+C'-a_{i+1}=K-(K-A)=A)，所以将 (K) 设为 (A) 即可。
同理于 (C)
至此，本题在线性的复杂度完美解决。
(Code:)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int N = 1e6 + 5 ;
int T, n, a[N] ;
signed main()
{
T = gi() ;
while( T-- ) {
n = gi() ;
rep( i, 1, n ) a[i] = gi() ;
int A = 0, B = 0, C = 0, ans = 0 ;
a[n + 1] = 0 ;
for(re int i = 1; i <= n; ++ i) {
a[i] -= min( A + B, a[i] ) ;
int ta = min( a[i], max( 0ll, a[i + 1] - A - C ) ), tb = max( 0ll, a[i] - max( 0ll, a[i + 1] - A - C ) ) ;
ans += (ta + tb), A += ta, B += tb ;
if( A + C > a[i + 1] ) {
int K = A + C - a[i + 1] ;
int ra = A - K, rc = C - K ;
if( ra < 0 ) C -= (K - A), K = A ;
if( rc < 0 ) A -= (K - C), K = C ;
A -= K, C -= K, ans -= K ;
}
swap( B, C ) ;
}
cout << ans << endl ;
}
return 0 ;
}