CF#574(Div.2)B. Sport Mafia

做完A题之后马上来做的B

感觉B比A简单多了

想了三分钟,推了两分钟,五分钟敲完代码,一遍过我膨胀了

这里是题意

对于每次放糖果的数量是一个等差数列1,2,3,4,5..x(这里的x是我们设的未知数,表示一共放了多少次糖果)

那么放入盒子里面的糖果的总值就是(1+x)*x/2 这个都求不来的话就去找高斯

一共有n次操作,我们设一共放入了x次糖果,那么剩下的(n-x)就是吃掉的糖果次数

因为每次吃一个,所以吃掉的糖果总数也是(n-x)

那么我们可以初步得到这样一个式子-> 放进去的-吃掉的=剩下的

转换成字母表达就是-> (1+x)*x/2-(n-x)=k

再去掉分母,移项合并得到关于x的一个式子

x^2+3=2(n+k)

因为x肯定是正整数.

所以左边部分是单调递增的,右边的两个参数n和k我们又已知

所以,二分的想法便油然而生了.

通过二分来得到x的值,如果左边小了就往大的二分,左边大了便往小的二分,一旦相等就说明当前这个x是我们想要的那个值

输出n-x就行了(别忘了要输出的是吃的糖果数量)

代码如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 50000
#define rg register
inline ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
ll sum;
ll n,k;
ll ans;
inline ll get_ans(ll x)
{
    return (x*x+3*x);
}
int main()
{
    n=read(),k=read();
    if(n==1) 
    {
        cout<<0;
        return 0;
    }
    sum=2*(n+k);
    ll l=1,r=n;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(get_ans(mid)==sum)
        {
            cout<<n-mid;
            return 0;
        }
        if(get_ans(mid)>sum)
        {
            r=mid-1;
        }
        else if(get_ans(mid)<sum)
        {
            l=mid+1;
        }
    }
}