我要评论 Dilhao 一共有 n 本教科书，每本教科书都有一个难度值，他每次出题的时候都会从其中挑两本教科书作为借鉴，如果这两本书的难度相差越大，Dilhao 出的题就会越复杂，也就是说，一道题的复杂程度等于两本书难度差的绝对值。
这次轮到 ldxxx 出题啦，他想要管 Dilhao 借 m 本书作为参考去出题，Dilhao 想知道，如果 ldxxx 在Dilhao给出的 m 本书里挑选难度相差最小的两本书出题，那么 ldxxx 出的题复杂程度最大是多少？
犀牛鬣蜥,苏州全城热恋2011,鬯薹鼍
二分是一种常用而且非常精妙的算法，常常是我们解决问题的突破口。二分的基本用途是在单调序列或单调函数中做查找操作。因此，当问题的答案具有单调性时，就可以通过二分把求解转化为判定（根据复杂度理论，判定的难度小于求解）。进一步的，我们还可以通过三分（适用于求解凸性函数）解决单峰函数的极值以及相关问题。
思想：分而治之。将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同，(如果子问题的规模仍然不够小,，再划分为k个子问题)，然后递归的求解这些子问题，最后用适当的方法将各个子问题的解合并成原问题的解。
方法：a）二分查找：在一个单调有序的集合或函数中查找一个解，每次分为左右两部分，判断解在哪个区间（并调节上下界），并直到找到目标元素。
int binary_search(int x) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (a[mid] == x) {
return mid;
}
if (a[mid] < x) {
l = mid + 1;
} else {
r = mid;
}
}
return - 1;
}
b）二分答案：（最大值最小或最小值最大这类问题）这类双最值问题常常选用二分法求解（二分之后，先假装自己确定答案），配合贪心，DP等算法，检验这个答案是否合理，将最优化问题转化为判定性问题。
c）代替三分：（对于单峰函数）二分导函数求函数极值。
例题：Bzoj1734 Poj2018 ... ...
借书（2018沈阳集训Day4）
#include <iostream>
#include <algorithm>
using namespace std;
long long diff[100010];
long long n, m, tmp, num_book;
bool check (long long x) {
num_book = 1;
long long tmp = diff[1];
long long flag_one = 1;
while (num_book < m) {
long long next = tmp + x;
long long flag = lower_bound(diff + flag_one, diff + n + 2, next) - diff;
if (flag == n + 1) {
return false;
}
num_book += 1;
flag_one = flag;
tmp = diff[flag];
}
return true;
}
int main() {
freopen("margin.in", "r", stdin);
freopen("margin.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> diff[i];
}
sort(diff + 1, diff + n + 1);
long long l = 0;
long long r = diff[n];
long long ans;
diff[n + 1] = 2 * diff[n];
while (l <= r) {
long long mid = (l + r) / 2;
if (check(mid) == true) {
ans = mid;
l = mid + 1;
} else if (check(mid) == false) {
r = mid - 1;
}
}
cout << ans << endl;
return 0;
}
适用于凸性函数的极值问题（二次函数就是一个典型的单峰函数）。与二分法强调函数的单调性不同，三分法强调函数的单峰性。
在区间 [L,R] [L,R] 中找两个三分点，也就是 mid 和 mmid，然后比较这两个点的 y 值大小。如果是计算最大值的情况，那么 y (mid) ≤ y (mmid)，说明最大值肯定在 mid 右边，这时把区间变成 [mid , R]，反之变成 [L , mmid] ，直到 LL 和 RR 很接近为止。如果是
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论