题面好长…

有质量的小题。首先要注意到一个结论,学生走的路线没有必要交叉,即可以看作前面一些人对付第一个寝管,后面的对付第二个,这样就独立成两个问题。

只有一个寝管就比较简单了,\(xjb\) 贪心就好了。能从后面运过来就运,不能就弃了这个寝室,全部移到下一个,有多往后运。

还注意到对付前面的人越多,\(x_1\) 单调不增,\(x_2\) 单调不降,显然 \(max\{x_1,x_2\}\) 是个下凸的,可以方便的二分求出 \(x_1=x_2\) 的最优点。就做好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005;
int n,D,B,ans=1e9,a[maxn],b[maxn],c[maxn],res1,res2,res;
bool check(int mid){
int now=mid;
for(int i=1;i<=n;i++) c[i]=a[i], b[i]=0;
for(int i=1;i<=n&&now;i++){
int t=min(now,c[i]); now-=t; c[i]-=t; b[i]+=t;
}
int sum; res1=0,res2=0;
sum=b[1];
for(int i=1,lst=1;i<=(n+1)/2;i++){
while(lst<n&&lst+1-i*D<=i) sum+=b[++lst];
if(sum<B) b[i+1]+=b[i], b[i]=0, res1++;
else if(b[i]>=B) b[i+1]+=b[i]-B, b[i]=B, sum-=B;
else b[lst]+=b[i]-B, b[i]=B, sum-=B;
}
sum=c[n];
for(int i=n,lst=n;i>=(n+1)/2+1;i--){
while(lst>1&&lst-1+(n-i+1)*D>=i) sum+=c[--lst];
if(sum<B) c[i-1]+=c[i], c[i]=0, res2++;
else if(c[i]>=B) c[i-1]+=c[i]-B, c[i]=B, sum-=B;
else c[lst]+=c[i]-B, c[i]=B, sum-=B;
}
ans=min(ans,max(res1,res2));
return res1>=res2;
}
int main(){
scanf("%d%d%d",&n,&D,&B);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int L=0,R=n*B;
while(L<=R){
int mid=(L+R)>>1;
if(check(mid)) res=mid, L=mid+1; else R=mid-1;
}
if(res<n*B) check(res+1);
printf("%d\n",ans);
return 0;
}