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

题号 NC112807
名称 Sand Fortress
来源 CF985D

题目描述

给你两个个数n和H，现在要求你求一个序列满足：

  1. 最左边的一个数的大小不超过H
  2. 相邻两个数之差的绝对值不超过1
  3. 所有数之和等于n

求这样一个序列的最小长度是多少？

样例

输入
5 2
输出
3
输入
6 8
输出
3
Here are the heights of some valid castles: 
n = 5, H = 2, [2, 2, 1, 0, ...], [2, 1, 1, 1, 0, ...], [1, 0, 1, 2, 1, 0, ...]
n = 6, H = 8, [3, 2, 1, 0, ...], [2, 2, 1, 1, 0, ...], [0, 1, 0, 1, 2, 1, 1, 0...] (this one has 5 spots occupied) 
The first list for both cases is the optimal answer, 3 spots are occupied in them.
And here are some invalid ones:
n = 5, H = 2, [3, 2, 0, ...], [2, 3, 0, ...], [1, 0, 2, 2, ...]
n = 6, H = 8, [2, 2, 2, 0, ...], [6, 0, ...], [1, 4, 1, 0...], [2, 2, 1, 0, ...]

算法

(二分)

显然如果序列中有0的话这个序列的长度可以无限大，

所以长度越长就越能找到合法的序列，这样似乎就有两段性，我们可以二分序列的长度

接着我们思考check函数怎么写

假设当前二分的长度是，

我们思考所有长度为的序列中，数字之和最大是多少

我们分两种情况来讨论：

如图：

图片说明

​ sum：

  1. (1) 当 （H + x） % 2 == 1

    ​ 如图:

    ​ 图片说明 

     sum：$h * h + h - (H * H - H) / 2 ,h = (x + H - 1) / 2 $

    (2) 当 （H + x） % 2 == 0

    ​ 如图：

    ​ 图片说明

    ​

    ​ sum：

得到sum后我们给出一个结论：

有了这个结论只要给出x求出sum,sum >= n返回true (答案小于等于x)，sum < n返回false (答案大于x)

下面给出证明：

  1. ,显然成立

  2. 我们给出一个操作可以得到一个长度为的数字之和为的合法序列：

    每一次我们将长度为数字之和为序列中的最大数字减一（如果有多个最大值任选一个减1）直到sum减少到n

    我们分类讨论一下：

    • 如果最大的数字在最左端，这个数字减1后依然小于H并且他右边的数字一定是小于等于它的减1后相差的绝对值依然是小于等于1
    • 最大的数字不在最左端，它两边的数字也一定是小于等于它的，减1后相差的绝对值依然是小于等于1

所以如果长度为的序列中，数字之和最大 >= n那么一定能构造出一个长度为的数字之和为n的合法序列

*本题主要关注一下__int128的输入输出

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
__int128 n,H;

__int128 read()
{
    __int128 x = 0,f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

inline void write(__int128 x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

bool check(__int128 x)
{
    if(H >= x)
    {
        return n <= x * (x + 1) / 2;
    }else
    {
        __int128 h;
        if((H + x) % 2 == 0)
        {
            h = (x + H) / 2;
            return n <= h * h - (H * H - H) / 2;
        }else
        {
            h = (x + H - 1) / 2;
            return n <= h * h + h - (H * H - H) / 2;
        }
    }
}

void solve()
{
    n = read(),H = read();
    __int128 l = 1,r = 1e18;
    while(l < r)
    {
        __int128 mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    write(l);
    puts("");
}

int main()
{
    /*#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL*/
    int T = 1;
    //init();
    //scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}