做完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; } } }