Sand Fortress

Sand Fortress

https://ac.nowcoder.com/acm/problem/112807

思路

挺简单的题...
二分答案.
因为凸函数价值最高,那么我们尽量凸起,然后ck一下,唯一的坑点就是会爆ll,这里的话使用__int128.

总的来说这题就是.

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
__int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')f=-1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}

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

__int128 n,k;
bool ck(__int128 u)//摆放u堆.
{
    if(u>n)    return true;
    if(u<=k)
    {
        return (1+u)*(u)/2>=n;
    }
    else
    {
        __int128 pos=(u-k+1);
        __int128 res=0;
        res+=(k)*(k-1)/2;
        if(pos&1)
        {
            __int128 a1=k,an=k+pos/2-1;
            res+=(a1+an)*(pos/2);
            res+=k+pos/2;
        }
        else
        {
            __int128 a1=k,an=k+pos/2-1;
            res+=(a1+an)*(pos/2);
        }
        return res>=n;
    }
}

int main()
{
    n=read(),k=read();
    __int128 l=1,r=1e18,ans=1e18;
    while(l<=r)
    {
        __int128 mid=(l+r)>>1;
        if(ck(mid))
        {
            r=mid-1;
            ans=min(ans,mid);
        }
        else    l=mid+1;
    }
    print(ans);
    return 0;
}
lpt的小屋 文章被收录于专栏

我想要一份甜甜的爱情

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-30 15:34
广州大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-16 02:48
门头沟学院_2022
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
3 收藏 评论
分享

全站热榜

正在热议