国家对网站建设补助,推广普通话的意义论文,做网站的找哪个,做雷达干扰的网站快速排序
题目1-整数二分-数的范围
给定一个按照升序排列的长度为 n 的整数数组#xff0c;以及 q 个查询。
对于每个查询#xff0c;返回一个元素 k 的起始位置和终止位置#xff08;位置从 0 开始计数#xff09;。
如果数组中不存在该元素#xff0c;则返回 -1 -1。…快速排序
题目1-整数二分-数的范围
给定一个按照升序排列的长度为 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
#includeiostreamusing namespace std;const int N 100010;int q[N];int n,m;int main(){cinnm;for(int i0;in;i) scanf(%d,q[i]);for(int i0;im;i){int x;cinx;int l0, rn-1;// 寻找左边界while(lr){int mid lr1;if(q[mid]x) rmid;else l mid1;}if(q[l]!x) cout-1 -1endl;//寻找右边界else{coutl ;int l0,rn-1;while(lr){int mid lr1 1;if(q[mid]x) lmid;else rmid-1;}coutrendl; //这里输出l和r都可以因为最终时刻l和r是指向一个位置的}}return 0;
}算法思想二分的主要思想是在一个区间内部去二分答案边界每次选择答案所在的区间进行处理每次区间缩小一半当区间长度为1的时候左右相等的时候就找到了答案。 整数划分需要注意边界问题 书写模板时候一定不要写错顺序就是先找左端点再找右端点。 //注意 1.mid一定要写在while循环的里面因为mid的值在while过程中是不断更新的。 2.找左端点时候更新方式midlr1; if(check) rmid; else lmid1; 3.找右端点时候更新方式midlr11; if(check) lmid; else rmid-1; 即 r与l对应取值的对应关系记住。
题目2 浮点数二分-数的三次方根
给定一个浮点数 n求它的三次方根。
输入格式 共一行包含一个浮点数 n。
输出格式 共一行包含一个浮点数表示问题的解。
注意结果保留 6 位小数。
数据范围 −10000≤n≤10000 输入样例 1000.00 输出样例 10.000000 #includeiostreamusing namespace std;int main(){double x;cinx;double l -10000, r 10000;while( r-l 1e-7){ //因为是浮点数二分随意不存在边界问题就不用1或-1double mid (lr)/2;if(mid*mid*mid x) lmid;else r mid;}printf(%.6f,l);return 0;
}算法思想浮点数二分对比整数二分不需要判断边界的情况所以更加简单。但是看似很简单的一道题有很多细节需要注意。 注意1.在判断r-l时数据范围必须要小于1e-6因为最后编译器判断时是保留小数点后六位的如果是1e-6可能导致小数点后第六位的数不同不能Accepted 2.在第一步确定数的范围时要设为-10000到10000而不能设为n。 3.在while进行判断的时候必须是右边界减去左边界或者取绝对值也可以。
