【BZOJ 2600】【IOI 2011】ricehub(贪心+中位数)
拿到这道题一开始有两个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