[CF949D]Curfew二分答案是个不错的开头，困难部分在于如何检查

传送门 to luogu

二分答案是个不错的开头&＃xff0c;困难部分在于如何检查。

考虑这样一种逃逸方式&＃xff1a;既然 $d\ge 1$ &＃xff0c;那么宿管是移动最慢的。在他即将锁门的时候&＃xff0c;跑到更居中的位置去。于是&＃xff0c;所有合格的寝室都居中。

两边都要搞定&＃xff0c;其实可以分开判断。就好比 $\mathtt{L}\mathtt{L}\mathtt{B}$ 上午学文化课&＃xff0c;可以考好&＃xff1b;下午学竞赛&＃xff0c;可以考好。那么二者都学好&＃xff0c;也是可以做到的。这里很重要的一点是&＃xff0c;总人数是一定足够的&＃xff0c;并且都可以用在某一边&＃xff08;不至于无所事事&＃xff09;。

用前缀和的方式&＃xff0c;求出在任意时刻&＃xff0c;能够到达宿管即将锁门的寝室的人有几个。然后就可以判断了。

此时回头看自己的 $\mathtt{i}\mathtt{f}$ 语句&＃xff0c;竟然是 xx<fi​ 的形式&＃xff0c;且 fif_ifi​ 与 $x$ 无关&＃xff01;那么我们可以改成 $\mathcal{O}(n)$ 的直接枚举。

#include
#include
#include
#include
#include
using namespace std;
inline int readint(){int a &＃61; 0; char c &＃61; getchar(), f &＃61; 1;for(; c<&＃39;0&＃39;||c>&＃39;9&＃39;; c&＃61;getchar())if(c &＃61;&＃61; &＃39;-&＃39;) f &＃61; -f;for(; &＃39;0&＃39;<&＃61;c&&c<&＃61;&＃39;9&＃39;; c&＃61;getchar())a &＃61; (a<<3)&＃43;(a<<1)&＃43;(c^48);return a*f;
}
template < class T >
void getMax(T&a,T b){ if(a < b) a &＃61; b; }
template < class T >
void getMin(T&a,T b){ if(b < a) a &＃61; b; }const int MaxN &＃61; 100002;
const int Mod &＃61; 998244353;
long long a[MaxN]; int d, b, n;void input(){n &＃61; readint(), d &＃61; readint();b &＃61; readint();for(int i&＃61;1; i<&＃61;n; &＃43;&＃43;i)a[i] &＃61; readint()&＃43;a[i-1];
}long long now[MaxN];
void solve(){long long ans &＃61; MaxN;for(int i&＃61;(n&＃43;1)/2; i; --i){int t &＃61; min(1ll*i*d&＃43;i,0ll&＃43;n);now[i] &＃61; now[i&＃43;1]; // 后缀getMax(now[i],i-a[t]/b);}for(int i&＃61;(n&＃43;1)/2&＃43;1; i<&＃61;n; &＃43;&＃43;i){int r &＃61; n-i&＃43;1, t;t &＃61; max(i-1ll*r*d-1,0ll);if(i !&＃61; (n&＃43;1)/2&＃43;1)now[i] &＃61; now[i-1]; // 前缀getMax(now[i],r-(a[n]-a[t])/b);}for(int x&＃61;0; x<&＃61;(n&＃43;1)/2; &＃43;&＃43;x){long long xez &＃61; now[x&＃43;1];getMax(xez,now[n-x]);getMin(ans,max(xez,0ll&＃43;x));}printf("%lld\n",ans);
}int main(){input(), solve();return 0;
}


再给出二分版的 check() &＃xff0c;可以对比二者的区别&＃xff1a;

for(int i&＃61;x&＃43;1; i<&＃61;(n&＃43;1)/2; &＃43;&＃43;i){if(1ll*i*d&＃43;i >&＃61; n) break;if(a[i*d&＃43;i]/b < i-x)return false;}for(int i&＃61;n-x; i>(n&＃43;1)/2; --i){int r &＃61; n-i&＃43;1;if(i-1ll*r*d <&＃61; 1) break;if((a[n]-a[i-r*d-1])/b < r-x)return false;}return true;