ACM - Sand Fortress - 二分

题目提交链接
牛客提交链接
CF提交链接

题意：
输入：n和H。求一个数列。数列限制条件：
（1）第一个数不超过H。
（2）第i个和第i+1个数的差值的绝对值不超过1，且数列长度为无穷大。
（3）数列中所有数的和为n
输出：这个数列可能有很多情况。输出这个数列长度的最小值。

分析：
数列长度最小，数列中所有的数的和一定 => 数列中的数尽可能大。
（1） => 初值限制。
（2） => 数有无穷多个，理解为结尾一定会出现 k，k-1，k-2，...，2，1 的情况。
所以，“尽可能大” => 数列中的最大值尽可能大 => 给定数列中的最大值，判断在给定的限制条件下能得到该数列的最大值。

二分条件的是否可行：
比如某个数列 k，k-1，k-2，...，2，1 的最大值 k 可行。
那么，k-1，k-1，k-2，...，2，1 的最大值 k-1 也可行。

所以根据题中限制条件，需要分为两类。自己试试边界数据就懂了。
（1）n特别小，H特别大。比如1 100000000。此时数列中的最大值由n控制。
（2）n特别大，H特别小。比如100000000 1。此时数列中的最大值由H控制。
于是分类。
当最大值x<=H时：
求和可行条件判断是：x,x-1,x-2,...1这个数列是否ok
当前数列最小为：x,x,x,...,2,1这个数列求和（如果多的不是x的倍数，随便加一个）
比如x=4，y=5，n=20。后四个数是4，3，2，1，还剩下来10，贪心往前面补足x，4，4，4，3，2，2，1（剩下的一定比x小，找地方放就好）
当最大值x>H时：
道理一样。
H,H+1,...,H+(x-H-1),x,x-1,...,1这个数列是否ok

#include<bits/stdc++.h>
using namespace std;

long long int n,H,ans;

long long int getsum(long long int x){
    if (x % 2 == 0)
        return (x / 2) * (x + 1);
    else
        return ( (x + 1) / 2) * x;
}

int ok(long long int x){
    long long int sum1 = getsum(x), sum2, Left;
    if (x <= H){
        if (sum1 > n) return 0;
        Left = n - sum1;
        if (Left % x == 0)
            ans = min(ans, x + Left / x);
        else
            ans = min(ans, x + Left / x + 1);
        return 1;
    }
    else{
        sum2 = getsum(x - 1) - getsum(H - 1);
        if (sum1 + sum2 > n) return 0;
        Left = n - sum1 - sum2;
        if (Left % x == 0)
            ans = min(ans, x + x - H + Left / x);
        else
            ans = min(ans, x + x - H + Left / x + 1);
        return 1;
    }
}


int main(){
    //freopen("input.txt", "r", stdin);
    ans = 1e18;
    scanf("%lld%lld", &n, &H);
    long long int l = 1, r = (long long int)sqrt(2.0 * n) + 10, mid;
    while(l <= r){
        mid = (l + r) / 2;
        if (ok(mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    printf("%lld\n", ans);
    return 0;
}