IOI 2011 米仓

Description: 在一条$x$轴上，有$n$个米仓，每个米仓的的粮食都是$1$，且知道它们的位置$p_i$，以及坐标范围$L$。问在某个点建一个仓库，在总花费不超过$B$的情况下，求最大的仓库粮食量，一粮食每一单位的运费为$1$。 $n\le 10^6,L\le 10^9,B\le 2\cdot 10^{15}$

Solution:

首先有一个$O(n^3)$的做法因为仓库只对一个区间$[l,r]$的米仓有影响模拟数据发现，它对花费的最优贡献一定是$(p_r-p_l)+(p_{r-1}-p_{l+1})...+(p_{mid+1}-p_{mid-1})$即仓库要建在中位数时最优。那么对于每个左端点$i$，我们可以线性找到它的右端点$j$，再利用前缀和求一个最优花费是否超过$B$即可。

Code:

#include<bits/stdc++.h> using namespace std; #define REP(i,f,t) for(int i=(f),i##_end_=(t);i<=i##_end_;++i) #define SREP(i,f,t) for(int i=(f),i##_end_=(t);i<i##_end_;++i) #define DREP(i,f,t) for(int i=(f),i##_end_=(t);i>=i##_end_;--i) #define ll long long template<class T>inline bool chkmin(T &x,T y){return x>y?x=y,1:0;} template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;} template<class T>inline void Rd(T &x){ x=0;char c; while((c=getchar())<48); do x=(x<<1)+(x<<3)+(c^48); while((c=getchar())>47); } const int N=1e5+2; int n,L; ll B; int p[N]; struct p20{ void solve(){ int ans=0; REP(i,1,n) REP(j,i+1,n) { int l=i,r=j; ll sum=0; while(l<r) sum+=p[r]-p[l],l++,r--; if(sum<=B) chkmax(ans,j-i+1); } printf("%d\n",ans); } }p1; struct p100{ ll sum[N]; bool check(int l,int r){ int mid=(l+r)>>1; ll cost=1ll*p[mid]*(mid-l+1)-(sum[mid]-sum[l-1])+sum[r]-sum[mid]-1ll*p[mid]*(r-mid); return cost<=B; } void solve(){ REP(i,1,n) sum[i]=sum[i-1]+p[i]; int j=1,ans=0; REP(i,1,n){ while(j<=n && check(i,j)) ++j; chkmax(ans,j-i); } printf("%d\n",ans); } }p2; int main(){ // freopen("ricehub.in","r",stdin); // freopen("ricehub.out","w",stdout); Rd(n),Rd(L),Rd(B); REP(i,1,n) Rd(p[i]); // if(n<=100)p1.solve();//O(n^3) // else p2.solve(); return 0; }