AcWing 289. 环路运输
原题链接
中等
作者:
东方晓
,
2022-02-25 14:08:29
,
所有人可见
,
阅读 248
// 破环成链 滑动窗口 单调队列
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6+5;
int n;
int w[N*2], f[N*2], q[N*2];
int main(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> w[i];
w[n+i] = w[i];
}
LL ans = 0;
int hh = 0, tt = -1;
for(int i = 1; i <= n*2; i ++){
if(hh <= tt && i-q[hh] > n/2) hh ++;
if(hh <= tt) ans = max(ans, (LL)w[q[hh]] + w[i] + i - q[hh]);
while(hh <= tt && w[q[tt]] - q[tt] <= w[i] - i) tt --;
q[++ tt] = i;
}
cout << ans << endl;
return 0;
}