Blue---二分算法(二分查找与二分答案)

牛可乐和魔法封印当区间具有二段性的时候就用二分来做。本题的意思就是找到数组中值为[x, y]区间的长度。由于是递增序列那么必然存在二段性直接用二分去做。唯一要注意的就是数组里可能不存在x或者y二分查找出来的必然是x的最小元素与y的最大元素因此分别查找出来的两个下标的元素也要算上它们也是属于[x, y]的所以区间长度的计算方式就是r-l1。#includeiostream using namespace std; const int N 1e5 10; int n; int a[N]; int find1(int x) { int l 1, r n; while(l r) { int mid l (r - l) / 2; if(a[mid] x) r mid; else l mid 1; } //如果元素全是小于x的就不合法了 if(a[l] x) return -1; return l; } int find2(int y) { int l 1, r n; while(l r) { int mid l (r - l 1) / 2; if(a[mid] y) l mid; else r mid - 1; } if(a[l] y) return -1; return l; } int main() { cin n; for(int i 1;i n;i) cin a[i]; int q 0; cin q; while(q--) { int x 0, y 0; cin x y; int l find1(x); int r find2(y); if(l ! -1 r ! -1) cout r - l 1 endl; else cout 0 endl; } return 0; }P1102 A-B 数对 - 洛谷题目的意思是找出所有满足A-BC的序列那移个项不就是要求我们找出所有满足等于BC的数字个数嘛如果序列是有序的话并且假设BC2的话那不就相当于找序列中2的个数嘛找到2的起始位置和结束位置不就相当于找到了嘛然后题目又说不同位置的数字一样的数对算不同的数对因此我们统计的时候用叠加去统计。所以思路就出来了排序二分。#includeiostream using namespace std; #includealgorithm typedef long long LL; LL n, c; const int N 2e5 10; LL a[N]; //找到序列中x的个数 int find(LL x) { int l 1, r n; while(l r) { int mid l (r - l) / 2; if(a[mid] x) r mid; else l mid 1; } //由于区间里可能根本没有x因此额外判断一下 int xl 0; if(a[l] ! x) return 0; xl l; l 1, r n; while(l r) { int mid l (r - l 1) / 2; if(a[mid] x) l mid; else r mid - 1; } int xr 0; if(a[l] ! x) return 0; xr l; //区间长度就是x的个数 return xr - xl 1; } int main() { cin n c; for(int i 1;i n;i) cin a[i]; sort(a 1, a 1 n); LL ret 0; for(int i 1;i n;i) { //A B C LL A a[i] c; ret find(A); } cout ret; return 0; }P1678 烦恼的高考志愿 - 洛谷注意如果发生越界访问加左右护法是一个好选择。#includeiostream using namespace std; #includealgorithm typedef long long LL; const int N 1e5 10; LL a[N]; int m, n; //找到离x最近的两个值返回最近的那个距离x的差值的绝对值 LL find(LL x) { //找到x的最小值 int l 1, r m; while(l r) { int mid l (r - l) / 2; if(a[mid] x) r mid; else l mid 1; } return min(abs(a[l - 1] - x), abs(a[l] - x)); } int main() { cin m n; for(int i 1;i m;i) cin a[i]; sort(a 1, a 1 m); a[0] -1e7; LL ret 0; for(int i 1;i n;i) { int x 0; cin x; //x就是每一次读取进来的高考估分 //这里有可能数值溢出 ret find(x); } cout ret; return 0; }P2440 木材加工 - 洛谷#includeiostream using namespace std; #includealgorithm typedef long long LL; const int N 1e5 10; LL n, k; LL a[N]; LL calc(LL mid) { LL sum 0; for(int i 1;i n;i) { //长度不够的话除完也是0 sum a[i] / mid; } return sum; } int main() { cin n k; for(int i 1;i n;i) cin a[i]; sort(a 1, a 1 n); LL l 1, r a[n]; //这里是从左往右len在增大获得的num在减小 //因此这里就变成了k左边kk右边k和博客里画的二分图正好反了 while(l r) { LL mid l (r - l 1) / 2; if(calc(mid) k) l mid; else r mid - 1; } //本题相当于是查找区间中k的最小k所对应的最大的len //有可能没有满足的情况要额外判断 if(calc(l) k) cout l endl; else cout 0 endl; return 0; }P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷#includeiostream using namespace std; typedef long long LL; const int N 1e6 10; int n, m; LL a[N]; LL calc(LL x) { LL ret 0; for(int i 1;i n;i) { if(a[i] x) ret a[i] - x; } return ret; } int main() { cin n m; for(int i 1;i n;i) cin a[i]; //题目给出的树的高度是4e5的所以其实可以不排序直接二分 LL l 1, r 4e5 10; while(l r) { LL mid l (r - l 1) / 2; if(calc(mid) m) l mid; else r mid - 1; } if(calc(l) m) cout l; else cout 0; return 0; }P2678 [NOIP 2015 提高组] 跳石头 - 洛谷#includeiostream using namespace std; typedef long long LL; const int N 5e4 10; LL L, n, m; LL a[N]; //最短跳跃距离为x时所要移走的岩石数 //calc天然就解决了担心的a[j]-a[i]mid直至j走到n1 //此时算出的sum会很大二分的时候必然会将这种情况过滤掉 LL calc(LL x) { LL sum 0; LL i 0, j 1; while(j n 1) { while(j n 1 a[j] - a[i] x) { j; } sum j - i - 1; i j; } return sum; } int main() { cin L n m; for(int i 1;i n;i) cin a[i]; //n表示起点到终点的岩石数不包括起点和终点 //因此还需要更新n到n1两块岩石之间的距离 //0~1这两块岩石间的距离就是a[1]所以不用去管了 a[n1] L; LL l 1, r L; while(l r) { LL mid l (r - l 1) / 2; if(calc(mid) m) l mid; else r mid - 1; } if(calc(l) m) cout l endl; return 0; }