大等于n的最小完全平方数 及 二分总结

问题描述

输出大等于n的最小的完全平方数。 若一个数能表示成某个自然数的平方的形式，则称这个数为完全平方数 Tips：注意数据范围

输入格式

一个整数n

输出格式

大等于n的最小的完全平方数

代码

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll n; cin >> n; if (n <= 0) cout << "0" << endl; else { ll l = 1, r = 9223372036854775800; while (l < r) { ll mid = (l + r) >> 1; if (mid >= (n*1.0)/ mid) //注意要将n转化为浮点型数据，不然做除法的时候会有舍入问题 r = mid; else l = mid + 1; } cout << l * l << endl; } return 0; }

二分模板总结

使用时不需要思考到底是将区间如何进行二分 只需要随意写一个check函数，判断其为真的条件 若l=mid则需要对mid进行修改 当l=mid时，r一定等于mid-1 当r=mid时，l一定等于mid+1

bool check(int x) {/* ... */} // 检查x是否满足某种性质 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1; } return l; } // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用： int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l; }

二分模板转载于acwing