线段树+二分,CF 431E - Chemistry Experiment

2024-08-25 00:52

本文主要是介绍线段树+二分,CF 431E - Chemistry Experiment,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解


一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

431E - Chemistry Experiment


二、解题报告

1、思路分析

贪心的考虑,如何加水可以让有水的瓶子的最大值最小?

选取一个上界top,低于top的瓶子我们先加到top,然后剩余的水平均加到这几个值为top的瓶子中

为了便于描述上述过程,我们不妨将瓶子的值非降序排序,记为val

那么每次相当于选择一个k,把h[0, k] 调整为h[k],多出来的水,平均给0~k这些瓶子

如果这是最优解,那么 (k + 1) * h[k] - sum(h{0, k}) <= v <= (k + 2) * h[k + 1] - sum(h(0l, k + 1))

令B[i] = (k + 1) * h[k] - um(h{0, k}),显然B[i] 单调递增,那么我们对于每个操作2,二分位置即可

B序列可以用线段树维护

2、复杂度

时间复杂度: O(nlogn + q log^2 n)空间复杂度:O(n + q)

3、代码详解

 ​
#include <bits/stdc++.h>using i64 = long long;
using i32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 998'244'353;template<class Info>
struct SegmentTree {int n;std::vector<Info> info;SegmentTree(int _n): n(_n), info(2 << (32 - __builtin_clz(_n))) {}template<class T>SegmentTree(std::vector<T>& _init): SegmentTree(_init.size()) {auto build = [&](auto&& self, int p, int l, int r) {if (l == r) {info[p] = _init[l];return;}int mid = l + r >> 1;self(self, p << 1, l, mid), self(self, p << 1 | 1, mid + 1, r);pull(p);};build(build, 1, 0, n - 1);}void pull(int p) {info[p] = info[p << 1] + info[p << 1 | 1];}void modify(int p, int l, int r, int x, const Info& v) {if (l == r) {info[p] = v;return;}int mid = l + r >> 1;if (x <= mid) modify(p << 1, l, mid, x, v);else modify(p << 1 | 1, mid + 1, r, x, v);pull(p);}void modify(int x, const Info& v) {modify(1, 0, n - 1, x, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (l > y || r < x) return Info();if (x <= l && r <= y) {return info[p];}int mid = l + r >> 1;return rangeQuery(p << 1, l, mid, x, y) + rangeQuery(p << 1 | 1, mid + 1, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 0, n - 1, l, r);}
};struct Info{i64 s = 0;int val = 0, sz = 0;friend Info operator+ (const Info &a, const Info &b) {if (!a.sz) return b;if (!b.sz) return a;return {a.s + b.s + 1LL * (b.val - a.val) * a.sz,b.val,a.sz + b.sz};}
};void solve() {int n, q;std::cin >> n >> q;std::vector<i64> h(n), val;for (int i = 0; i < n; ++ i)std::cin >> h[i], val.push_back(h[i]);std::vector<std::array<i64, 2>> o(q);for (int i = 0, op; i < q; ++ i) {std::cin >> op;if (op == 1) {std::cin >> o[i][0] >> o[i][1];-- o[i][0];val.push_back(o[i][1]);}else {o[i][0] = -1;std::cin >> o[i][1];}}std::ranges::sort(val);val.erase(std::unique(val.begin(), val.end()), val.end());std::map<i64, int> mp;std::vector<Info> info(val.size());for (int i = 0; i < val.size(); ++ i)mp[val[i]] = i, info[i].val = val[i];for (int x : h)++ info[mp[x]].sz;SegmentTree<Info> sgt(info);for (auto &[p, v] : o) {if (~p) {int i = mp[h[p]];-- info[i].sz;sgt.modify(i, info[i]);i = mp[h[p] = v];++ info[i].sz;sgt.modify(i, info[i]);}else {int lo = -1, hi = val.size();while (lo + 1 < hi) {int x = lo + hi >> 1;if (sgt.rangeQuery(0, x).s <= v)lo = x;elsehi = x;}auto t = sgt.rangeQuery(0, lo);std::cout << std::fixed << std::setprecision(10) << 1.0 * (v - t.s) / t.sz + t.val << '\n';}}}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
}();int main () {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endifint T = 1;// std::cin >> T;while (T --) {solve();}return 0;
}

这篇关于线段树+二分,CF 431E - Chemistry Experiment的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1104096

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c