竞赛讨论区 > 【每日一题】2021年3月19日题目精讲
头像
王清楚
编辑于 2021-03-24 16:25
+ 关注

【每日一题】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. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

全部评论

(8) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐