国庆做题记录（基础算法）

这篇文章信息量偏大，请谨慎阅读，注意高效利用右边的目录。
其他部分咕咕咕地更新中……敬请期待
1.1 二分 & 双指针

关联博文：Atserkcn-0/1分数规划
P1404 平均数

既然要让子串平均数最大，那就二分平均数，判断能否达到即可。复杂度 \(O(n\log V)\)。
关联题目：[2025国庆集训Day2C] course
点击查看代码

1. signed main(){
2.         read(n), read(m);
3.         for(register int i = 1; i <= n; i++) read(a[i]), a[i] *= 10000, Max = max(Max, a[i]);
4.         int l = 0, r = Max;
5.         while(l <= r) {
6.                 int mid = (l + r) >> 1;
7.                 bool flag = 0; int minn = 0;
8.                 for(register int i = 1; i <= n; i++) {
9.                         s[i] = s[i - 1] + (a[i] - mid);
10.                         if(i >= m) {
11.                                 minn = min(minn, s[i - m]);
12.                                 if(s[i] > minn) {
13.                                         flag = 1;
14.                                         break;
15.                                 }
16.                         }
17.                 }
18.                 if(flag) l = mid + 1;
19.                 else r = mid - 1;
20.         }
21.         fwr(l / 10);
22.         return 0;
23. }

复制代码

P4047 [JSOI2010] 部落划分

要求距离最远的部落距离最小，依然二分答案。但是判定时需要贪心地选择最近的两个部落合并，需要用到并查集维护集合。时间复杂度 \(O(n^2\log V\times \alpha(n))\)。
点击查看代码[code]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