Part1.2 基础算法-二分与三分

A愤怒的牛

二分答案

#include <bits/stdc++.h>using namespace std;const int N = 100010;int n, m;
int a[N];inline bool check(int mid)
{
    int cnt = 1;int t = a[0] + mid;for (int i = 1; i < n; i ++ ){
    if (a[i] < t) continue;else{
    cnt ++;t = a[i] + mid;}}return cnt >= m;
}
int main()
{
    cin >> n >> m;for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);sort(a, a + n);int l = 0, r = 1e9;while (l < r){
    int mid = (l + r + 1)>> 1;if (check(mid)) l = mid;else r = mid - 1;// cout << mid << endl;}cout << r << endl;return 0;
}

Best Cow Fences

一开始想的时候，找不到具有单调性的数据。我在想，平均值是要求的，长度，前缀和，都不具有单调性啊，但最后发现，其实求使使用的平均值作为二分的根据。。。。

#include <cstdio>
#include <algorithm>
using namespace std;const int N = 100010;
const double esp = 1e-5;int n, k;
double a[N], s[N];bool check(double mid)
{
    for (int i = 1; i <= n; i ++ ){
    s[i] = s[i - 1] + a[i] - mid;}//求区间长度大于k的s的最大值double mn = 3e10, mx = -3e10;for (int i = k; i <= n; i ++ ){
    //mn是我们求得的，与i距离至少为k的最小值//那么最小值后面的值，一定会上升，我们要找的就是这么多mn = min(mn, s[i - k]);mx = max(mx, s[i] - mn);}return mx >= 0.0;
}
int main()
{
    scanf("%d%d", &n, &k);for (int i = 1; i <= n; i ++ ){
    scanf("%lf", &a[i]);}//二分平均值double l = -10000000, r = 20000000;while (r - l > esp){
    double mid = (l + r) / 2;if (check(mid)) l = mid;else r = mid;}printf("%d\n", (int)(r * 1000));// cout << (int)(l * 1000) << endl;return 0;
}

曲线

三分，我就一直在想一个问题，那个量是单谷函数呢，s绝对是，后来发现，因为连续性，F也是一个单谷函数。。。。

#include <cstdio>
#include <algorithm>using namespace std;const int N = 100010, inf = 1 << 30;
const double eps = 1e-6;int n;
double a[N], b[N], c[N];double f(double x)
{
    double ans = -inf;for (int i = 1; i <= n; i ++ )ans = max(ans, a[i] * x * x + b[i] * x + c[i]);return ans;
}
void work()
{
    scanf("%d", &n);for (int i = 1; i <= n; i ++ ){
    scanf("%lf%lf%lf", &a[i], &b[i], &c[i]);}double l = 0, r = 1000;while (r - l > eps){
    double d = (r - l) / 3;double mid1 = l + d, mid2 = r - d;if (f(mid1) > f(mid2)) l = mid1;else r = mid2;}printf("%.4lf\n", f(r));
}int main()
{
    int T; scanf("%d", &T);while (T -- ){
    work();}return 0;
}

数列分段 II

最大值最小化问题，具有满足二分性，可以二分做。

#include <cstdio>using namespace std;typedef long long ll;const int N = 100010, inf = 1 << 30;int n, m;
int a[N];bool check(int mid)
{
    ll sum = 0, cnt = 1;for (int i = 1; i <= n; i ++ ){
    if (a[i] > mid) return false;if (sum + a[i] > mid){
    sum = 0;cnt ++;}sum += a[i];}return cnt <= m;
}
int main()
{
    scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++  )scanf("%d", &a[i]);int l = 0, r = inf;while (l < r){
    int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}printf("%d\n", r);return 0;
}

扩散

这一题，用二分我是怎么也没有看出来的，看题解，人家将n个坐标看成n个点，然后每两个点之间的曼哈顿距离当作两点之间的距离，对Floyd算法做了下变形，dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]))
解释，这像几滴墨水扩展一样，如果只有两地x和y，那么他俩相遇的最短时间就是他们之间曼哈顿距离上取整然后整除2的结果，这很好理解。如果有三滴墨水呢，假设x和z比较近，y和z也比较近。x和z的距离，与y和z的距离很好求解，就是d1, d2,然后我们来看x和y的距离怎么计算。可能是x和y两个相互扩展得到的距离d3更近，也可能是两个点x和y先扩展到z更近，因为x和y都扩展到了z，那么x、y、z就是一个连通块了【看到连通块，可以引出我们另一个方法，二分加并查集】，所以这个距离就是max(d1, d2)所以两者总和起来就是我们上面的那个公式了。
而且我们这么搞，点数只有n个，n的三次方完全可以。下面是代码

而你一开始思考的，想用宽搜搜一遍，dist数组记录到达每个点的步数，然后每拓展完一次就要再用一次flood fill算法判断一下是否当前图形已经连通了，如果每连通就接着搜，如果连通了，就可以推出循环了，本来觉得50大的图可以随便搜，但是，忽然看到xy的大小都是1e9的，凉凉。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef pair<int, int> PII;#define x first
#define y secondconst int N = 55;int n;
PII a[N];
int dist[N][N];int get(PII a, PII b)
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}int main()
{
    scanf("%d", &n);for (int i = 1; i <= n; i ++ )scanf("%d%d", &a[i].x, &a[i].y);memset(dist, 0x3f, sizeof dist);for (int i = 1; i <= n; i ++ )for (int j = i + 1; j <= n; j ++ ){
    dist[i][j] = dist[j][i] = get(a[i], a[j]);}for (int k = 1; k <= n; k ++ )for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]));int ans = 0;for (int i = 1; i <= n; i ++ )for (int j = i + 1; j <= n; j ++ )ans = max(ans, dist[i][j]);printf("%d\n", (ans + 1) / 2);return 0;
}

我们到这里已经更深的理解了题意，题目让我们求的就是两点之间的最大的最短距离，很像二分
我们可以这么做，二分距离，如果两个点在一个连通块中就说两个点已经扩展过了， 就不需要再管了，如果两个点没有在一个连通中，我们就看一下它的曼哈顿距离是否小于等于2倍的mid，如果是，就将它加入连通块中，如果不，就跳过。
我们最后遍历一遍并查集，如果只有一个连通块，那就true，说明mid可以更小，如果不是一个连通块，那就false，说经mid要变大一些。
代码如下：

#include <cstdio>
#include <algorithm>using namespace std;typedef pair<int, int> PII;#define x first
#define y secondconst int N = 55, inf = 1 << 30;int n;
PII a[N];
int fa[N];int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}int get(PII a, PII b)
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}void init()
{
    for (int i = 1; i <= n; i ++ ) fa[i] = i;
}bool check(int mid)
{
    init();for (int i = 1; i <= n; i ++ )for (int j = i + 1; j <= n; j ++ ){
    int d = get(a[i], a[j]);int x = find(i), y = find(j);if (x == y) continue;//i和j已经在一个连通块中了if (d <= 2 * mid) fa[x] = y;}int cnt = 0;for (int i = 1; i <= n; i ++ )if (fa[i] == i) cnt ++;return cnt == 1;
}int main()
{
    scanf("%d", &n);for (int i = 1; i <= n; i ++ )scanf("%d%d", &a[i].x, &a[i].y);int l = 0, r = inf;while (l < r){
    int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}printf("%d\n", r);return 0;
}

F 灯泡

不太知道为啥x的左边界是那样取得，说是为了墙上有影子，但是一定要墙上有影子吗？

#include <cstdio>using namespace std;const double eps = 1e-6;double H, h, D;double f(double x)
{
    double sum = D + H;return sum - (x + (H - h) * D / x);
}void work()
{
    scanf("%lf%lf%lf", &H, &h, &D);double l = (H-h)*D/H, r = D;while (r - l > eps){
    double d = (r - l) / 3;double mid1 = l + d, mid2 = r - d;if (f(mid1) > f(mid2)) r = mid2;else l = mid1;}printf("%.3lf\n", f(r));
}
int main()
{
    int T;scanf("%d", &T);while (T -- ){
    work();}return 0;
}

传送带

三分套三分，据说，在AB间固定一点E的时候，根据这个点E，在CD上有一点F，会让EF+FD为一个单谷函数，可以三分出谷底，然后通过这个值，在三分E，最后E和F会让AE+EF+FD达到最小。。。玄学，还没想懂为什么？

#include <cstdio>
#include <cmath>
using namespace std;struct Node
{
    double x, y;
}a, b, c, d;
double p, q, r;double dist(Node a, Node b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double get(Node f, Node e)
{
    // double d1 = dist(a, e) / p;double d2 = dist(d, f) / q;double d3 = dist(e, f) / r;// return d1 + d2 + d3;return d2 + d3;
}double f(Node e)
{
    Node left(c), right(d);int cnt = 100;while (cnt -- )//循环100次足以将精度确定{
    Node mid1, mid2;mid1.x = left.x + (right.x - left.x) / 3;mid1.y = left.y + (right.y - left.y) / 3;mid2.x = right.x - (right.x - left.x) / 3;mid2.y = right.y - (right.y - left.y) / 3;if (get(mid1, e) > get(mid2, e)) left = mid1;else right = mid2;}return dist(a, e) / p + dist(e, right) / r + dist(right, d) / q;
}int main()
{
    scanf("%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y);scanf("%lf%lf%lf%lf", &c.x, &c.y, &d.x, &d.y);scanf("%lf%lf%lf", &p, &q, &r);Node left(a), right(b);// printf("%lf %lf\n", left.x, left.y);// printf("%lf %lf\n", right.x, right.y);int cnt = 100;while (cnt -- ){
    Node mid1, mid2;mid1.x = left.x + (right.x - left.x) / 3;mid1.y = left.y + (right.y - left.y) / 3;mid2.x = right.x - (right.x - left.x) / 3;mid2.y = right.y - (right.y - left.y) / 3;if (f(mid1) > f(mid2)) left = mid1;else right = mid2;}printf("%.2lf\n", f(right));return 0;
}