[CF] D. Sand Fortress - Educational Codeforces Round 44 (Rated for Div. 2)
Solutions Codeforces 贪心 二分 2100 Med
Lastmod: 2025-01-30 周四 00:55:12

https://codeforces.com/contest/985/problem/D

题目大意

输出最小的序列 h 的长度 l，满足

  1. hi≥0
  2. h0≤H
  3. hl−1=1
  4. ∑h=n
  5. |hi−hi−1|≤1

其中 1≤n,H≤1018。

简要题解

因为我们想要序列尽量短，因此我们想每个 hi 尽量大。如果没有 h 的限制，会是这样：

 \
   \
     \

显然我们可以二分这个最大数 p 使得这个等差数列的和 s≤n（其实 p 也是数量）。s<n 时由于这已经是 p 个能达到的极限了，显然构造 p+1 个刚好可以满足 n。因为此时 n−s≤p，否则 p 可以更大，因为这些值在等差数列中都出现了，因此只要把这个插值，插入到对应的值旁边就不会破坏 |hi−hi−1|≤1。

 \
   \
     -
       \

当 H≥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√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;
}
Prev: [CF] E. Pencils and Boxes - Educational Codeforces Round 44 (Rated for Div. 2)
Next: [CF] B. Switches and Lamps - Educational Codeforces Round 44 (Rated for Div. 2)

Gitalking ...