国庆做题记录（基础算法）
这篇文章信息量偏大，请谨慎阅读，注意高效利用右边的目录。其他部分咕咕咕地更新中……敬请期待
1.1 二分 & 双指针
关联博文：Atserkcn-0/1分数规划
P1404 平均数
既然要让子串平均数最大，那就二分平均数，判断能否达到即可。复杂度 \(O(n\log V)\)。
关联题目： course
点击查看代码signed main(){
read(n), read(m);
for(register int i = 1; i <= n; i++) read(a), a *= 10000, Max = max(Max, a);
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 = s + (a - mid);
if(i >= m) {
minn = min(minn, s);
if(s > 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 : fa = find(fa); }double mx, my; inline bool chk(double mid) { for(register int i = 1; i 不错，里面软件多更新就更好了
页:
[1]