本题数据量较大，用并查集把移走挡板后联通的几个池子合并成一个连通块，求某个池子的蓄水量，只需向上找其祖宗的值和池子总数即可。（每个连通块中，编号大的池子为编号小的节点的父亲）
#include<bits/stdc++.h>
using namespace std;
#define int
展开全文
首先因为隔板的存在，所以整个水池开始是一坨一坨的，一共有 坨。
操作 就是把所有与 有交集的坨坨拿来进行合并，合并结果为总水量除以总池子数。
考虑用 set 维护，这样查询就是严格 级别的，我们来分析修改操作。
由于每次合并坨数都会减少 ，所以最多合并 次，均摊下来总复杂度为 ，这样总复杂
展开全文
不使用高级数据结构，仅用最基础算法的一个优雅的写法
思路：区间合并+前缀和
n,m=map(int,input().split())
pool=[0]+list(map(int,input().split()))
s=[0]*(n+10) #前缀和
for i in range(1,n+1):
展开全文
D&E线段树做法
#include <iostream>
#include <iomanip>
using namespace std;
int a[200005];
struct elem {
double val;
int l,r;
};
struct
展开全文
小苯的蓄水池线段树写法求debug:能过样例但零分
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
double t[N];
double up[N],s[N];
double n,m;
void bui
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
