P1404 平均数
既然要让子串平均数最大，那就二分平均数，判断能否达到即可。复杂度 \(O(n\log V)\)。
关联题目：[2025国庆集训Day2C] course
点击查看代码
signed main(){ read(n), read(m); for(register int i = 1; i <= n; i++) read(a[i]), a[i] *= 10000, Max = max(Max, a[i]); int l = 0, r = Max; while(l <= r) {int mid = (l + r) >> 1; bool flag = 0; int minn = 0; for(register int i = 1; i <= n; i++) {s[i] = s[i - 1] + (a[i] - mid); if(i >= m) {minn = min(minn, s[i - m]); if(s[i] > minn) {flag = 1; break; }} } if(flag) l = mid + 1; else r = mid - 1; }fwr(l / 10);return 0;
}
P4047 部落划分
要求距离最远的部落距离最小，依然二分答案。但是判定时需要贪心地选择最近的两个部落合并，需要用到并查集维护集合。时间复杂度 \(O(n^2\log V\times \alpha(n))\)。
点击查看代码
int find(register int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);
}
double mx, my;
inline bool chk(double mid) {for(register int i = 1; i <= n; i++) fa[i] = i; int cnt = 0; for(register int i = 1; i <= n; i++) for(register int j = 1; j <= n; j++) {if((x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]) <= mid) {fa[find(i)] = find(j); }} for(register int i = 1; i <= n; i++) if(find(i) == i) cnt++; return cnt >= k;
}
int main(){read(n); read(k); for(register int i = 1; i <= n; i++) {read(x[i]), read(y[i]);mx = max(1.0 * x[i], mx), my = max(1.0 * y[i], my); } double l = 0, r = mx * mx + my * my, mid; while(r - l > 1e-4) {mid = (l + r) / 2; if(chk(mid)) l = mid; else r = mid; } printf("%.2lf\n", sqrt(l)); return 0;
}
P6004 Wormhole Sort S
奶牛为什么要钻虫洞？
要求最大化被奶牛用来排序的虫洞宽度的最小值，还是二分答案。