Codeforces Round #404 (Div. 2) C 二分查找

Codeforces Round #404 (Div. 2)

题意:对于 n and m (1 ≤ n, m ≤ 10^18)  找到

  1) [n<= m] cout<<n;

  2) [n>m]最小的 k => (k -m) * (k-m+1) >= (n-m)*2 成立

思路:二分搜索

	#include <bits/stdc++.h>
#include <map>
using namespace std; #define LL long long
const long long INF = 1e10;
long long n, m, del, mix;
bool cal(long long a){
return a*(a+1) >= del;
} long long find(long long l, long long r){
while(l + 1 < r){
long long mid = (l +r) >> 1;
// cout<<(l+r)/2<<" "<<l<<" "<<r<<endl;
if(cal(mid)) r = mid;
else l = mid;
}
return l;
} int main(){
ios::sync_with_stdio(false); cin.tie(0);
// freopen("input2.txt", "r", stdin);
cin>>n>>m; if(n <= m) cout<<n<<endl;
if(n > m){
del = 2 * (n-m);
mix = find(0, 1e10);
while(!cal(mix)) mix++;
cout<<mix+m<<endl;
}
return 0;
}

  

上一篇:Codeforces Round #404 (Div. 2)A,B,C


下一篇:Codeforces Round #404 (Div. 2) C. Anton and Fairy Tale 二分