企业官网建设流程全解析

牛可乐和魔法封印

当区间具有二段性的时候就用二分来做。本题的意思就是找到数组中值为[x, y]区间的长度。由于是递增序列，那么必然存在二段性，直接用二分去做。唯一要注意的就是数组里可能不存在x或者y，二分查找出来的必然是>=x的最小元素与<=y的最大元素，因此分别查找出来的两个下标的元素也要算上，它们也是属于[x, y]的，所以区间长度的计算方式就是r-l+1。

#include<iostream> 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-B==C的序列，那移个项不就是要求我们找出所有满足等于B+C的数字个数嘛，如果序列是有序的话，并且假设B+C==2的话，那不就相当于找序列中2的个数嘛，找到2的起始位置和结束位置不就相当于找到了嘛，然后题目又说不同位置的数字一样的数对算不同的数对，因此我们统计的时候用+=叠加去统计。所以思路就出来了排序+二分。

#include<iostream> using namespace std; #include<algorithm> 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 烦恼的高考志愿 - 洛谷

注意：如果发生越界访问，加左右护法是一个好选择。

#include<iostream> using namespace std; #include<algorithm> 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 木材加工 - 洛谷

#include<iostream> using namespace std; #include<algorithm> 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左边>=k，k右边<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 / 砍树 - 洛谷

#include<iostream> 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 提高组] 跳石头 - 洛谷

#include<iostream> 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走到n+1 //此时算出的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到n+1两块岩石之间的距离 //0~1这两块岩石间的距离就是a[1]，所以不用去管了 a[n+1] = 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; }