如果我二分内判断 g[n] <= p
,二分外 l = mid + 1,ret = mid
,那么就过了。
il bool check__(int val) {
hh = 1; tt = 0; f[0] = g[0] = 0;
rep(i,1,n) {
// cerr << hh << " " << tt << endl;
while (hh <= tt && check(q[hh - 1],q[hh]) <= i) ++ hh;
int j = q[hh - 1];
f[i] = f[j] + calc(j + 1,i) - val; g[i] = g[j] + 1;
while (hh <= tt && check(q[tt - 1],q[tt]) >= check(q[tt],i)) -- tt;
q[++ tt] = i;
}
return g[n] <= p;
}
il void solve() {
//------------code------------
read(n,p);
rep(i,1,n) read(a[i]);
sort(a + 1,a + n + 1);
rep(i,1,n) s[i] = s[i - 1] + a[i];
int l = -1e7,r = 0,ret = 0;
while (l <= r) {
int mid = l + r >> 1;
if (check__(mid)) l = mid + 1,ret = mid;
else r = mid - 1;
}
check__(ret);
write(f[n] + p * ret,'\n');
return ;
}
但是如果我反过来,二分里判断 g[n] >= p
,二分外移动 r = mid - 1,ret = mid
,那么就会 wa 20pts.
不理解为什么。求教。