Part 2.3 二分答案

题单

P1024 [NOIP2001 提高组] 一元三次方程求解

思路

因为每个零点之间的“距离”>=1且任意一个零点属于[-100,100]，所以我们可以进行枚举，具体看代码。

代码

#include 
using namespace std;
double a, b, c, d;
int num;
double check (double x) //计算函数值
{return (a * x * x * x + b * x * x + c * x + d);
} 
int main ()
{scanf ("%lf %lf %lf %lf", &a, &b, &c, &d);for (double i = -100; i <= 100; i++) //枚举左端点{double l = i, r = i + 1, mid;if (check (l) == 0) //检验左端点是否为零点{printf ("%.2lf ", l);num ++;continue; //若左端点为零点，则右端点一定为零点，而这一轮的右端点会成为下一轮的左端点，故可不用检验右端点是否为零点}double fl = check (l), fr = check (r);if (fl * fr < 0) //零点存在定理{while (r - l >= 0.001) //0.001控制精度，开始二分答案{mid = (l + r) / 2;double fm = check (mid);if (fm * fl <= 0) {r = mid;}else {l = mid;}}printf ("%.2lf ", l);num ++;} if (num == 3) //有了3个零点后即可停止。{break;}}return 0;
}
//时间复杂度约为O(2000)

P2678 [NOIP2015 提高组] 跳石头

思路

如果我们穷举模拟拿去哪几块石头，这个题的时间复杂度会相当高；但是这个题给出了答案的有界性与单调性，答案的有界性即答案一定属于[1, l]，其中l是终点到起点的距离；答案的单调性即答案要的是最短距离的最大值，也就是最短距离合理的情况下越大越好，故我们可以想到二分答案。如果这个答案合理，那我们记录下这个答案（因为他可能是最终答案）并试试比他更大的答案；如果不合理，那我们试试比他更小的答案，知道循环条件不再成立。那怎么判断一个答案是否合理呢？那我们可以用人下一个要去的石子与当前所在石子之间的差与这个答案进行比较：如果大于等于这个答案，那么我们直接走到下一个石子；如果小于这个答案，而已知这个答案是最短距离，那么说明我们该拆这个下一个石子了，并将下一个石子变为这个下一个石子的下一个石子。若最后拿走的石子数小于等于m则合理，否则不合理。 算下来，时间复杂度为O(nlogl)。

代码

#include 
using namespace std;
const int maxn =  50005;
int l, n, m, d[maxn], ans;
bool check (int x) 
{int now = 0, tot = 0, i = 0; //i记录下一个石子，now记录当前所在的是石子，tot记录被拿走的石子总数。while (i < n + 1) //当i等于n+1的时候就可以结束了{i ++;if (d[i] - d[now] < x) //当i==n+1时，若d[i]-d[now]>=x还好说，因为可以直接走过去；那d[i]-d[now]{tot ++; //拿走第i个石子}else{now = i; //跳到第i个}}if (tot > m) //拿走的比之多拿走的还多，就不合理{return false;}return true;
}
int main ()
{scanf ("%d %d %d", &l, &n, &m);for (int i = 1; i <= n; i++) {scanf ("%d", &d[i]);}d[0] = 0, d[n + 1] = l; //不要忘了初始化int ll = 1, r = l;while (ll <= r) //二分{int mid = (ll + r) / 2;if (check (mid)) {ans = mid; //记下这个可行的答案ll = mid + 1; }else{r = mid - 1;	}}printf ("%d", ans);return 0;
}

收获

①弄懂了答案的有界性与单调性什么意思，知道了二分答案的一种使用条件。
②一篇教二分的好文章。

P1902 刺杀大使

思路

首先我们发现这个题很假的一个地方，即“必须到达第 n 行的每个房间”这句话，乍一看，我们以为是要找n条路径，然后再取max {p1, p2, ……，pn}，pi表示第n条路径的经过的房间的最大值作为这一方案的答案，然后再从这些方案中取最小值。但是我们发现，第n行的p[n][j]全为0，这说明我们只需要找能到达第n行的路径即可，可是我们发现这样和看错题就无差别了，时间复杂度都特别高。但是，我们发现，我们要的答案满足有界性与单调性，即ans一定介于最小的p[i][j]与最大的p[i][j]之间，ans我们要的是最大值中的最小值，那么二分答案的思路不久出来了嘛？至于合不合理，那我们只需要找到一条能从(1, 1)通到第n行的路径即可，用DFS？显然不好，因为我们不需要找到所有路径；没错！ 用BFS求是否连通!若能找到路径，则这个答案合理；否则不合理。这样时间复杂度就是O(10n)了。

代码

#include 
using namespace std;
const int maxn = 1005;
int n, m, p[maxn][maxn], l, r, ans, vis[maxn][maxn]; 
int dx[5] = {0, 0, 1, 0, -1};
int dy[5] = {0, 1, 0, -1, 0};
bool check (int d) //bfs求（1， 1）与第n行是否可连通
{queue <pair <int, int>> q;q.push (make_pair (1, 1));memset (vis, 0, sizeof (vis));vis[1][1] = 1;while (q.size ()) {int x = q.front().first;int y = q.front().second;q.pop ();for (int i = 1; i <= 4; i++) {int nx = x + dx[i];int ny = y + dy[i];if (nx < 1 || nx > n || ny < 1 || ny > m || p[nx][ny] > d || vis[nx][ny] == 1) {continue;}q.push (make_pair (nx, ny));vis[nx][ny] = 1;if (nx == n) return true;} }return false;
}
int main ()
{scanf ("%d %d", &n, &m);l = 2147483647, r = -2147483647;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {scanf ("%d", &p[i][j]);r = max (r, p[i][j]);l = min (l, p[i][j]);}}while (l <= r) {int mid = (l + r) / 2;if (check (mid)) {ans = mid;r = mid - 1;}else {l = mid + 1;}}printf ("%d", ans);return 0;
}

收获

①重学了如何用BFS求是否连通
②证明了ans一定是p[i][j]中的某一个：已知答案为p[i][j]中的某一个，并把正确答案记为A；若现在的ans > A，则根据程序，r被赋值为mid - 1，由A为正确答案，所以此时l一定小于A，于是A便会被包含在新的更小的[l,r]中；若ans < A，则ans一定不合理，根据程序，l被赋值为mid + 1，此时r一定大于A，于是A便会被包含在新的更小的[l,r]中。所以无论现在的ans与A的大小关系如何，随着二分的一次次进行，A会被包含在越来越小的[l,r]中，直至l>=r,此时A=ans=mid。

P1314 [NOIP2011 提高组] 聪明的质监员

思路

根据题意，我们不难发现，在一定范围内，随着W的增大，y的值在减小；而且当Wmax{w[i]}时，y不再随W的改变而改变。，于是因为W有单调性和有界性，使得y也有单调性和有界性。故，我们使用二分答案，二分时W的界。那我们应该下一步写check（）函数了，我们肯定想要随着W的[l, r]区间的缩小，使得y值“尽量”更接近s值，故我们判断的指标就出来了：y与s谁大。那我们怎么求y呢？暴力的话，但这一步时间复杂度O(mn)，直接超时；因为求和区间连续，所以我们可以想到前缀和，将时间复杂度降为O(max {m, n})。那么问题又来了，最后得到的一个y是否就是答案？其实是不是的。其实这个题也可以看作求大于z的最小y和小于z的最大y，两次二分答案即可。 故综合时间复杂度为O(max {m, n} * log(max{w[i]} - min {w[i]}))。

代码

#include 
using namespace std;
const int maxn = 200005;
long long n, m, li, ri, l[maxn], r[maxn], w[maxn], v[maxn];
long long s, ans, y;
long long prew[maxn], prea[maxn];
bool check (int W) 
{y = 0;memset (prew, 0, sizeof (prew));memset (prea, 0, sizeof (prea));for (int i = 1; i <= n; i++) //特别巧妙地前缀和{if (w[i] >= W) {prew[i] = prew[i - 1] + 1;prea[i] = prea[i - 1] + v[i];}else {prew[i] = prew[i - 1];prea[i] = prea[i - 1];}}for (int i = 1; i <= m; i++) {y += (prew[r[i]] - prew[l[i] - 1]) * (prea[r[i]] - prea[l[i] - 1]);}if (y >= s) {y -= s;return true;}else {y = s - y;return false;}
}  
int main ()
{li = 1000005, ri = -1;scanf ("%lld %lld %lld", &n, &m, &s);for (int i = 1; i <= n; i++) {scanf ("%lld %lld", &w[i], &v[i]);li = min (li, w[i]);ri = max (ri, w[i]);}for (int i = 1; i <= m; i++) {scanf ("%lld %lld", &l[i], &r[i]);}long long ans = 9223372036854775807;while (li <= ri){int mid = (li + ri) / 2;if (check (mid)){li = mid + 1;}else {ri = mid - 1;}ans = min (ans, y);//要每次最小的|y-s|}printf ("%lld", ans); return 0;
}

P1083 [NOIP2012 提高组] 借教室

思路

emm，先吐槽一下，屑第一次看成每天m个订单了，导致题目做不出来，哭唧唧T_T这个题如果直接暴力（循环记录每天被需要的总教室数然后与每天的空余教室数比较）的话，时间复杂度可以达到O(nm)，很明显超时；但是，我们发现，订单时具有有界性与单调性的，其有界性体现在其一定属于[1,m]；其单调性体现在假设无法全部满足，若已知前a单无法满足，那么前a+1单跟无法满足，故我们可以对订单数进行二分答案。那么判断这个前a单是否合理的依据是什么？显然是这前a单是否可以得到满足。那么就需要我们某天剩余的教室数与我们这a单需要的教室数进行比较，若这n天全是剩余的教室数大于等于需要的，那么合理，合理了就可以试试后a天可不可以，即：l = mid + 1；否则r = mid - 1那么怎么统计每天需要的教室数？暴力显然不可。那我们想什么可以对连续区间内的元素进行统一处理的呢？差分可以！于是我们的check()函数就完成了。对此，此题的复杂度是O(max {m, n} * logm)

代码

#include 
using namespace std;
const int maxn = 1000005;
long long n, m, r[maxn], d[maxn], s[maxn], t[maxn], need[maxn], diff[maxn], ans; 
bool check (int x) 
{memset (diff, 0, sizeof (diff));memset (need, 0, sizeof (need));for (int i = 1; i <= x; i++) //差分简化改变数据的时间复杂度{diff[s[i]] += d[i];diff[t[i] + 1] -= d[i];}for (int i = 1; i <= n; i++) {need[i] = need[i - 1] + diff[i];if (need[i] > r[i]) {return false;}}return true;
}
int main ()
{scanf ("%lld %lld", &n, &m);for (int i = 1; i <= n; i++) {scanf ("%lld", &r[i]);}for (int i = 1; i <= m; i++) {scanf ("%lld %lld %lld", &d[i], &s[i], &t[i]);}int l = 1, ri = m;if (check (m)) //如果发现前m单都可，那说明都能满足，故输出0即可。{printf ("0");return 0;}	while (l <= ri) {int mid = (l + ri) / 2;if (!check (mid)) //前面做的题都是真则统计答案，但是这个题要的是第一个“不能”完成的订单。{ans = mid;ri = mid - 1;}else {l = mid + 1;}}printf ("-1\n%lld", ans);return 0;
}

收获

①再识差分。
②原来二分答案对象可以这么隐蔽，单调性可以是这样的。

P4343 [SHOI2015]自动刷题机

思路

很显然，这个题就是对n进行二分答案，因为n具有单调性即当n越大，切题数一般会越小（“一般”的意思是可能不变）；但这个题很离谱的一个地方是，n的有界性太模糊了，不知道最大的n是多少，姑且认为是long long吧。，那我们发现其实我们要的就是可行n（使切题数等于k的n）的最小值和最大值，那我们两次二分答案就好了，但是这个题的特色是check（）函数，这个题，我们的check（）函数返回的不再是两个值，而是三个值，对应切题数与k之间的三种大小关系，不难想我们只有当这两个量相等的时候才记录答案。时间复杂度为O(log(1e18) * l)

代码

#include 
using namespace std;
const int maxn = 100005;
long long ansi = -1, ansii = -1, k;
int l, x[maxn];
int check (long long m) //特殊的check（）函数
{long long cur = 0, tot = 0;for (int i = 1; i <= l; i++) {cur = max (cur + x[i], 0ll);if (cur >= m) {tot ++;cur = 0;if (tot > k) {return 0;}}}if (tot == k) return 1;else return 2;
}
int main ()
{scanf ("%d %lld", &l, &k);for (int i = 1; i <= l; i++) {scanf ("%d", &x[i]);}long long li = 1, ri = 1e18;while (li <= ri) //这个二分答案真的像是缩小区间和找最有答案的合体。{long long mid = (li + ri) / 2;if (check(mid) == 1){ansi = mid;ri = mid - 1;} else if (check (mid) == 0) {li = mid + 1;}else {ri = mid - 1;}}li = 1, ri = 1e18;while (li <= ri) {long long mid = (li + ri) / 2;if (check(mid) == 1){ansii = mid;li = mid + 1;} else if (check (mid) == 0) {li = mid + 1;}else {ri = mid - 1;}}if (ansi == -1) {printf ("-1");return 0;}printf ("%lld %lld\n", ansi, ansii);return 0;
}

收获

①见识了一种新的二分答案类型。

最后的总结

1）什么时候用二分答案

题目中有一个量具有有界性和单调性，且对这个量进行二分答案可以有效减小时间复杂度

2）量单调性的体现有哪几种

①题目中另一个量随着这个量在其界内的增大而单调变化
②题目中的另一个量的变化（比如说满足与否，合理与否，存在与否）以这个量的某一个值为变化的“阈值”

3）我们会用哪些知识辅佐二分（不全）？

数学知识、BFS、前缀和、差分……

4）二分答案的作用是什么

①我们可以用它来确定有明确判断条件的最优解，通常是可行解中的最大值或最小值
②我们可以用它来缩小区间，减小与标准值之间的的误差，比如说|y-s|和零点

5）一个误区

二分答案的对象不一定是最后答案本身，但一定与答案有某种定量关系。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！