「CH 5501」环路运输 (单调队列 + 断环成链)

CH 5501
题意:给定$n$长数列$a$,找出最大的$a_i+a_j+min(|i-j|, n - |i-j|)$

$min(|i-j|, n - |i-j|)$也就是逆时针或顺时针从 $i$ 到 $j$ 中较近的一种。
所以我们将环断开成一条链,然后在链上就不用讨论$min$。因为对于原串如果存在$i,j$使得$i-j \geq n / 2$,那么$min(|i-j|, n - |i-j|)=i-j$。同理在链上也一样,且$i-j \leq n / 2$时相当于在两串中间的区间。$a_i+a_j+i-j$,移项处理一下,我们只用维护$a_i-i$的最大值。因为是区间移动,所以单调队列维护。

知识点:
1、单调队列的写法

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 1000000 + 5;
int n, a[MAXN * 2];
int l, r, que[MAXN * 4], ans = 0;
void clean() {
}
int solve() {
clean();
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i + n] = a[i];
l = 1, r = 1;
for (int i = 1; i <= 2 * n; ++i) {
while (l <= r && que[l] < i - n / 2) ++l;
ans = max(ans, i + a[i] + a[que[l]] - que[l]);
while (l <= r && a[que[r]] - que[r] <= a[i] - i) --r;
que[++r] = i;
}
cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------