拿到这道题一开始有两个naive的想法
想法1：对于每个位置 向右扩展 直到不能取了为之 但是又觉得复杂度不对就放弃了...... 想法2：离散化坐标 二分仓库的位置 每次往左右两边数量较多的一边靠（这是什么口胡玩意儿？？？）
正解：
事实证明我是被ioi2011吓到了
其实就是想法1加了一丢丢东西 维护一个左指针 右指针 假设是[l,r]区间 那么仓库放的位置最优一定是中位数的地方 这样枚举l的话 r是单调递增的
然后注意奇奇怪怪的边界
#include<bits/stdc++.h> #define N 100005 #define int long long using namespace std; template<class T> inline void read(T &x) { x=0; static char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } int R,L,B,x[N],sum[N]; int l,r,ans; inline int check(int l,int r) { int m=(l+r)>>1; int sum1=sum[r]-sum[m]-(r-m)*x[m]; int sum2=x[m]*(m-l)-(sum[m-1]-sum[l-1]); return sum1+sum2; } main() { read(R),read(L),read(B); for(int i=1;i<=R;i++) read(x[i]),sum[i]=sum[i-1]+x[i]; for(l=1;l<R;l++) { while(r<R&&check(l,r+1)<=B) r++; //拓展右指针 ans=max(ans,r-l+1); } cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9867742.html
