企维多类似网站,足球比赛直播现场在线观看,做网站 英语,青岛知名设计公司文章目录算法模板整数二分算法模板浮点数二分算法模板模板题数的范围原题链接题目题解数的三次方根原题链接题目题解算法模板
整数二分算法模板
bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid 1, r]时使用#xff1a;
int b…
文章目录算法模板整数二分算法模板浮点数二分算法模板模板题数的范围原题链接题目题解数的三次方根原题链接题目题解算法模板
整数二分算法模板
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;
}浮点数二分算法模板
bool check(double x) {/* ... */} // 检查x是否满足某种性质double bsearch_3(double l, double r)
{const double eps 1e-6; // eps 表示精度取决于题目对精度的要求一般比题目要求精度取小两个次方比较保险如要求1e-6则取1e-8while (r - l eps){double mid (l r) / 2;if (check(mid)) r mid;else l mid;}return l;
}
模板题
数的范围
原题链接
https://www.acwing.com/problem/content/791/
题目
789 . 数的范围 给定一个按照升序排列的长度为 n 的整数数组以及 q 个查询。
对于每个查询返回一个元素 k 的起始位置和终止位置位置从 0 开始计数。
如果数组中不存在该元素则返回 -1 -1。
输入格式 第一行包含整数 n 和 q表示数组长度和询问个数。
第二行包含 n 个整数均在 1∼10000 范围内表示完整数组。
接下来 q 行每行包含一个整数 k表示一个询问元素。
输出格式 共 q 行每行包含两个整数表示所求元素的起始位置和终止位置。
如果数组中不存在该元素则返回 -1 -1。
数据范围 1≤n≤100000 1≤q≤10000 1≤k≤10000 输入样例
6 3
1 2 2 3 3 4
3
4
5输出样例
3 4
5 5
-1 -1题解
#include iostream
using namespace std;const int N 1e6 10;
int n,m;
int q[N];int main(){scanf(%d%d,n,m);for(int i0;in;i) scanf(%d,q[i]);while(m--){int x; cinx;int l 0,r n-1;while(l r){int mid lr1;if(q[mid]x) r mid;else l mid 1;}if(q[l] ! x) cout-1 -1endl;else{coutl ;int l 0,r n-1;while(lr) {int mid lr1 1;if(q[mid]x) l mid;else r mid - 1;}coutlendl;}}return 0;
}数的三次方根
原题链接
https://www.acwing.com/problem/content/792/
题目
790 . 数的三次方根 给定一个浮点数 n求它的三次方根。
输入格式 共一行包含一个浮点数 n。
输出格式 共一行包含一个浮点数表示问题的解。
注意结果保留 6 位小数。
数据范围 −10000≤n≤10000 输入样例
1000.00输出样例
10.000000题解
#include iostream
#include math.h
using namespace std;
int main(){double n;cin n;double l -10000, r 10000;while(r-l 1e-8){ //一般精度比要求精度再多两个次方比较保险double mid (lr) / 2 ;if(pow(mid,3)n) r mid;else l mid;}printf(%.6lf,l);return 0;
}
