【二分】Codeforces Round #404 (Div. 2) C. Anton and Fairy Tale

时间:2022-07-04 18:37:33

当m>=n时,显然答案是n;

若m<n,在第m天之后,每天粮仓减少的量会形成等差数列,只需要二分到底在第几天,粮仓第一次下降到0即可。

若直接解不等式,可能会有误差,需要在答案旁边扫一下。

注意二分上界的确定,不能太小也不能太大。

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
ll n,m;
int main(){
	cin>>n>>m;
	if(m>=n){
		cout<<n<<endl;
		return 0;
	}
	ll S=n-m;
	ll l=1,r=2000000000ll;
	while(l<r){
		ll mid=(l+r)/2ll;
		if(mid*mid+mid>=S*2ll){
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<<m+l<<endl;
	return 0;
}