【记录】[COCI 2009/2010 #4] OGRADA

P5186 [COCI 2009/2010 #4] OGRADA - 洛谷 (luogu.com.cn)搞两次滑动窗口第一次是范围内求最小第二次是最小值数组里求最大。判断和思路都挺新奇的放一下。还有开 long long 和小心爆数组。#includebits/stdc.h using namespace std; #define int long long const int N 1e6 1e5 10; int a[N], q[N]; int b[N], ans[N]; signed main () { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; for (int i 1; i n; i ) { cin a[i]; } int h 1, t 0; q[0] 0; memset(b, 0, sizeof(b)); for (int i 1; i n; i ) { while (a[i] a[q[t]] t h) { t --; } t ; q[t] i; while (q[t] - q[h] m h t) { h ; } b[i] a[q[h]]; } h 1, t 0; q[0] 0; for (int i m; i n m - 1; i ) { while (b[i] b[q[t]] t h) { t --; } t ; q[t] i; while (q[t] - q[h] m h t) { h ; } ans[i - m 1] b[q[h]]; } int sum 0, res 0; for (int i 1; i n; i ) { sum (a[i] - ans[i]); } int last 0, id 0; for (int i 1; i n; i ) { if (ans[i] ! last || i - id m) { last ans[i]; id i; res ; } } cout sum \n res \n; return 0; }