当前位置：首页 > news >正文

做题记录（Part 1. 基础算法）

news 2026/6/13 1:42:36

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;
}