https://codeforces.com/contest/985/problem/D
题目大意
输出最小的序列 $h$ 的长度 $l$，满足
- $h_i \ge 0$
- $h_0 \le H$
- $h_{l - 1} = 1$
- $\sum h = n$
- $|h_i - h_{i - 1}| \le 1$
其中 $1 \le n, H \le 10^{18}$。
简要题解
因为我们想要序列尽量短，因此我们想每个 $h_i$ 尽量大。如果没有 $h$ 的限制，会是这样：
\
\
\
显然我们可以二分这个最大数 $p$ 使得这个等差数列的和 $s \le n$（其实 $p$ 也是数量）。$s < n$ 时由于这已经是 $p$ 个能达到的极限了，显然构造 $p + 1$ 个刚好可以满足 $n$。因为此时 $n - s \le p$，否则 $p$ 可以更大，因为这些值在等差数列中都出现了，因此只要把这个插值，插入到对应的值旁边就不会破坏 $|h_i - h_{i - 1}| \le 1$。
\
\
-
\
当 $H \ge p$ 时我们都可以用上述的解。
当 $H < p$ 时，由于题目的一顿描述，很容易误以为，只能构造出这样的东西
H ---
\
\
-
\
然后写出如下代码 WA 一发
void solve() {
LL n, h; cin >> n >> h;
LL l = 1, r = 2e9;
LL mid, ans = 1;
while (l <= r) {
mid = (l + r) >> 1;
if ((mid + 1) * mid / 2 <= n) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if (ans <= h) {
if (ans * (ans + 1) / 2 < n) {
ans++;
}
cout << ans << '\n';
return;
}
// h < ans
ans = h;
n -= h * (h + 1) / 2;
ans += (n + h - 1) / h;
cout << ans << '\n';
}
但实际上可以是这样
/\
/ \
H / \
\
\
同理我们可以分析这个形状的上限（因为无法用同样的 $l$ 塞入更多的值了）。注意顶上的元素可以有一个或者两个（也可以不分类只讨论单最值的情况，如果这样的情况补充一个元素不够的话，则变为双顶，加某中间平台元素即可）。
复杂度
$T$：$O(\log \sqrt{n})$
$S$：$O(1)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
LL n, h; cin >> n >> h;
LL l = 1, r = 2e9;
LL mid, ans = 1;
while (l <= r) {
mid = (l + r) >> 1;
if ((mid + 1) * mid / 2 <= n) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if (ans <= h) {
if (ans * (ans + 1) / 2 < n) {
ans++;
}
cout << ans << '\n';
return;
}
// h < ans
l = h + 1; r = 2e9;
LL mx = h;
while (l <= r) {
mid = (l + r) >> 1;
LL sum = (1 + mid) * mid / 2;
sum += (h + mid - 1) * (mid - 1 - h + 1) / 2;
if (sum <= n) {
mx = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
ans = mx + (mx - h);
LL sum = (1 + mx) * mx / 2;
sum += (h + mx - 1) * (mx - 1 - h + 1) / 2;
if (n - sum > mx) {
ans++;
}
if (n - sum > 0) {
ans++;
}
cout << ans << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] B. Switches and Lamps - Educational Codeforces Round 44 (Rated for Div. 2)