神贪心……写了一个晚上加一个早上。
先考虑只有一个宿管的情况。
- 首先，如果这个宿舍人多了，多余的人就跑到下一个宿舍。（如果这是最后一个宿舍的话，多的就躺床底下）
- 如果这个宿舍人少了，但是能从别的宿舍调过来人，那就调人。
- 如果这个宿舍人少了，从别的宿舍也调不过来足够的人，那就全跑到下一个宿舍去。
- 让宿管查宿。
关于调人，我们可以每次总是从当前能调过来人的最远宿舍调人，调成负的也无所谓。想一想，为什么。
还有一个神奇的事情：不同的人的路径不交。比如说，有 (i leq a leq b leq j)，要是 (i) 跑到 (b)，(j) 跑到 (a)，就不如 (i) 去 (a)，(j) 去 (b)。
因此，有这样一个宿舍：这个宿舍左边的人都去对付第一个宿管，右边的人都去对付第二个宿管，这个宿舍的人有去对付第一个的也有去对付第二个的。
或者说，我们枚举有多少个人对付第一个宿管。每次枚举都 (mathrm{O}(n)) 的求一下，总复杂度是 (mathrm{O}(n^2b))，这样不好，考虑加速枚举。
可以发现，分去对付第一个宿管的人越多，宿管发现的赖宿舍数越少。
记 (f(m)) 是给第一个宿管分去 (m) 人然后发现的赖宿舍数，显然 (f(m)) 是非严格单调减的。记 (g(m)) 是给第一个宿管分去 (m) 人（也就是给第二个宿管分 (nb-m) 人）然后第二个宿管发现的赖宿舍数，显然 (g(m)) 是非严格单调增的。
欲最小化 (max(f(m),g(m)))，则记 (z(m)=g(m)-f(m))，则 (z(m)) 非严格单调增。二分找出那个合适的 (m) 即可。
需要注意的一点是，如果 (z(m)=0) 那当然好，那样答案就是 (ans(m))。可是我们在二分的时候写的判定是 (z(m) geq 0) 这种，有可能找出来的是 (z(m) > 0) 的最小 (m)，因此还要看看 (ans(m-1))，看看到底哪个更小。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int aa[100005], n, d, b, qq[100005], cur=1, a[100005], mid;
int f(int hmn, int far){
int r=1, sum=0, re=0;
for(int i=1; i<=hmn; i++){
for(; r<=far && r<=i+d*i; r++)
sum += a[r];
if(a[i]>=b){
int tmp=a[i]-b;
a[i] -= tmp;
a[i+1] += tmp;
sum -= a[i];
}
else{
if(sum>=b){
a[r-1] -= b - a[i];
a[i] = b;
sum -= a[i];
}
else{
a[i+1] += a[i];
a[i] = 0;
re++;
}
}
}
return re;
}
int z(int x, int &tmp1, int &tmp2){
while(qq[cur-1]>=x && cur>1) cur--;
while(qq[cur]<x && cur<n) cur++;
memset(a, 0, sizeof(a));
for(int i=1; i<=cur; i++)
a[i] = aa[i];
a[cur] = x - qq[cur-1];
tmp1=f((n+1)/2, cur);
memset(a, 0, sizeof(a));
for(int i=n; i>=cur; i--)
a[n-i+1] = aa[i];
a[n-cur+1] = qq[cur] - x;
tmp2=f(n/2, n-cur+1);
return tmp2-tmp1;
}
int main(){
cin>>n>>d>>b;
for(int i=1; i<=n; i++){
scanf("%d", &aa[i]);
qq[i] = qq[i-1] + aa[i];
}
int l=0, r=n*b, re, tmp1, tmp2;
while(l<=r){
mid = (l + r) >> 1;
if(z(mid, tmp1, tmp2)>=0) re = mid, r = mid - 1;
else l = mid + 1;
}
z(re, tmp1, tmp2);
int ans=max(tmp1,tmp2);
z(re-1, tmp1, tmp2);
ans = min(ans, max(tmp1, tmp2));
cout<<ans<<endl;
return 0;
}
upd：从神犇代码学的
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, cnt1, cnt2, b, d;
ll a[100005];
ll sum(ll l, ll r){
if(l<1) l = 1;
if(r>n) r = n;
return a[r] - a[l-1];
}
int main(){
cin>>n>>d>>b;
for(int i=1; i<=n; i++){
scanf("%I64d", &a[i]);
a[i] += a[i-1];
}
for(int i=1; i<=n/2; i++){
if(sum(1, i+(ll)i*d)>=(ll)(cnt1+1)*b) cnt1++;
if(sum(n-i-(ll)i*d+1, n)>=(ll)(cnt2+1)*b) cnt2++;
}
cout<<max(n/2-cnt1, n/2-cnt2);
return 0;
}