【每日一题】2021年3月19日题目精讲

题号 NC112807
名称 Sand Fortress
来源 CF985D
每日一题三期汇总贴~


如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：开开心心写

题意：
输入：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;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目3月26日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴