「一本通 1.2 练习 2」扩散
显然联通块的个数是随时间越来越少的。
所以可以二分时间。
经过一波运算，可以得出两点需要联通的时间是
(abs(x[i] - x[j]) + abs(y[i] - y[j]) + 1) / 2
然后每次用并查集维护一下联通分块就好了。
第一次写这种开结构体的并查集，感觉很酷炫。
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 60;
int dis[MAXN][MAXN], x[MAXN], y[MAXN];
int maxt, n;struct Disjoint_Set
{int f[MAXN], sum;void init() { _for(i, 1, n) f[i] = i; sum = n;}int find(int x){if(f[x] != x)f[x] = find(f[x]);return f[x];}void Union(int a, int b) { int aa = find(a), bb = find(b);if(aa != bb){f[aa] = bb;sum--;}}
}S;bool check(int t)
{S.init();_for(i, 1, n)_for(j, i + 1, n)if(dis[i][j] <= t)S.Union(i, j);return S.sum == 1;
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d%d", &x[i], &y[i]);_for(i, 1, n)_for(j, i + 1, n){int d = (abs(x[i] - x[j]) + abs(y[i] - y[j]) + 1) / 2;dis[i][j] = dis[j][i] = d;maxt = max(maxt, d);}int l = -1, r = maxt;while(l + 1 < r){int m = (l + r) >> 1;if(check(m)) r = m;else l = m;} printf("%d\n", r);return 0;
}poj 2018
这道题是一道好题。
首先可以二分平均数，把最优问题转化成判定性问题
然后可以预处理，把每个数减去平均数，只要最终的结果大于等于0就可以了，这个很秀。
最后要解决一个问题，求一个子序列，它的和最大，子序列的程度不小于L
我们可以枚举终点i，然后就转化成0 <= j <= i - L中 最小的[j, i - L]
每次枚举的时候j的范围只会加1，所以我们可以直接在枚举的时候更新答案。
注意最后输出要转化一下类型。
#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e5 + 10;
double a[MAXN], s[MAXN];
int n, L;bool check(double m)
{ _for(i, 1, n) s[i] = s[i - 1] + a[i] - m;double ans = -1e12, min_val = 1e12; _for(i, L, n){min_val = min(min_val, s[i - L]);ans = max(ans, s[i] - min_val);}return ans >= 0;
}int main()
{scanf("%d%d", &n, &L);_for(i, 1, n) scanf("%lf", &a[i]); double l = -2001, r = 2001;while(r - l > 1e-8){double m = (l + r) / 2;if(check(m)) l = m;else r = m;}printf("%d\n", int(r * 1000));return 0;
}