首页 > 代码库 > Codeforces Round #404 (Div. 2) C 二分查找
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) C 二分查找
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。