2017年ACM模板（常用）弱渣整理 二、二分

lower_bound

lower_bound 这个函数是从已经排好序的序列a中利用二分搜索找出指向满足ai >= k的ai的最小的指针,注意是指针。upper_bound函数类似，就是求出满足ai > k的ai的最小的指针。

#include<cstdio> #include<algorithm> using namespace std; int a[100]; int main() { printf("输入序列个数：\n"); int k; scanf("%d",&k); printf("输入序列:\n"); for(int i=0; i<k; i++) { scanf("%d",&a[i]); } sort(a, a+k); printf("输入查找的数：\n"); int t; scanf("%d",&t); printf("lower_bound:%d\n",lower_bound(a, a+k, t)-a); printf("upper_bound:%d\n",upper_bound(a, a+k, t)-a); return 0; }

因为lower_bound函数是查询 ai >= k 的最小的指针。 而upper_bound函数是查询ai > k的最小的指针，那么就可以通过这个差异求出序列a中k的个数： upper_bound(a, a+n, k) - lower_bound(a, a+n, k)

---

问题一、最大化最小值

M为放置的个数

bool C(int d) { int last = 0; for(int i=1; i<M; i++) { int crt = last + 1; while(crt<N && x[crt] - x[last] < d) { crt++; } if(crt == N) return false; last = crt; } return true; }

问题二、最大化平均值

bool C(double d) { for(int i=0; i<n; i++) { y[i] = v[i] - d * w[i]; } sort(y, y+n); double sum = 0; for(int i=0; i<k; i++) { sum += y[n-i-1]; } return sum >= 0; }

问题三、寻找第k大值

bool C(int d) { int cnt = 0; for(int i=0; i<N; i++) { cnt += (upper_bound(a+i, a+N, a[i]+d)-1 - (a+i)); } if(cnt >= M) return true; else return false; }

类似这种二分套二分的思想，二分第k大的值统计<=k的个数，与k相比较来缩小范围。