Description
在一条环形公路旁均匀地分布着N座仓库,编号为1~N,编号为 i 的仓库与编号为 j 的仓库之间的距离定义为 dist(i,j)=min(|i-j|,N-|i-j|),也就是逆时针或顺时针从 i 到 j 中较近的一种.每座仓库都存有货物,其中编号为 i 的仓库库存量为 Ai.在 i 和 j 两座仓库之间运送货物需要的代价为 Ai+Aj+dist(i,j).求在哪两座仓库之间运送货物需要的代价最大.1≤N≤10^6,1<=Ai<=10^7.
Sol
断环为链,再复制一段到末尾
枚举i,我们只需要找到一个在[i-N/2,i-1]之间找到一个j使得(a[j]-j)最大,就求出了当前的最大代价.
找j当然不能枚举(N的范围就在上面),可以用单调队列维护.
具体来说,双端单调队列的队头放的是a[j]-j的最大值,以及j值(即它的序号),每次i++,把j超过范围(<i-N/2)的移出队列,把队列里比a[i-1]-(i-1)小的移出队列,再将a[i-1]-(i-1)加入队列,最后取出队头,即使当前a[j]-j的最大值.
如果关于单调队列的部分不明白,建议做Luogu1886滑动窗口
至于双端,用deque辣QwQ
Code
这题的code还是很好实现的 : ) 好久没有一遍过了QwQ
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #define Rg register 5 #define il inline 6 #define go(i,a,b) for(Rg int i=a;i<=b;++i) 7 using namespace std; 8 il int read() 9 { 10 int x=0,y=1;char c=getchar(); 11 while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();} 12 while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();} 13 return x*y; 14 } 15 const int N=1e6+1; 16 int n,m,ans,a[N*2]; 17 deque<int>q; 18 int main() 19 { 20 n=read();m=n<<1; 21 go(i,1,n)a[i]=a[n+i]=read(); 22 go(i,2,m) 23 { 24 while(q.size()&&i-q.front()>n/2)q.pop_front(); 25 while(q.size()&&a[i-1]-i>a[q.back()]-q.back())q.pop_back(); 26 q.push_back(i-1); 27 ans=max(ans,a[i]+i+a[q.front()]-q.front()); 28 } 29 printf("%d ",ans); 30 return 0; 31 }