淄博网站制作网络服务,课程网站建设调研报告,专业企业建站公司,建一个产品介绍网站题解#xff1a;CF1918D#xff08;D. Blocking Elements#xff09;
一、 读题
1. 题目链接
#xff08;1#xff09; 洛谷链接
洛谷链接
#xff08;2#xff09; CF链接
CF链接
2. 题意简述
已知一个长度为 n n n 的数组 a a a#xff0c;构造一个数组 b…题解CF1918DD. Blocking Elements
一、 读题
1. 题目链接
1 洛谷链接
洛谷链接
2 CF链接
CF链接
2. 题意简述
已知一个长度为 n n n 的数组 a a a构造一个数组 b b b记其长度为 m m m使得代价最小。代价为①和②的最大值。 ① ∑ i 1 n a b i ①\sum_{i1}^{n}a_{b_i} ①i1∑nabi ② max 0 ⩽ i ⩽ m ∑ j b i 1 b i − 1 1 a j ②\max_{0\leqslant i\leqslant m}\sum_{jb_{i}1}^{b_{i-1}1}a_j ②0⩽i⩽mmaxjbi1∑bi−11aj 这里我们规定 b 0 b n 1 1 b_0b_{n1}1 b0bn11。
二、 分析
本题 n n n 为 1 0 5 10^5 105 数量级是标准的 O ( n ⋅ l o g 2 ( n ) ) O(n·log_{2}(n)) O(n⋅log2(n)) 题。
三、 知识
二分答案动态规划前缀和单调队列优化。
四、 思路
由于本题需要同时保证两个量①和②最优所以一定是确定其中一个并用已知的这一个去求未知的。我们不难想到可以已知②求①。这里我们利用可行性进行二分答案即通过 j u d g e judge judge 函数判断在保证②最大为 n u m num num 的情况下能得到的最小的①是否比 n u m num num 小用二分答案找到“行”与“不行”的分界点。
那么如何验证呢
我们不难想到动态规划——定义 f i f_{i} fi 为考虑 a a a 中的前 i i i 个数保证②不超过 n u m num num并且选择了 a i a_i ai在这种情况下①的最小值。
转移也不难对于 f i f_{i} fi我们在从 1 1 1 到 i − 1 i-1 i−1 的范围内选择一个 j j j使得从 ∑ k j i a k \sum_{kj}^ia_k ∑kjiak 不超过 n u m num num这样 f i f_i fi 就可以从所有 f j f_j fj 加上 1 1 1 转移当然这里是求最小值。但是遍历的代价是平方级的所以这里用前缀和单调队列优化。
为了方便计算和统计答案我们定义 a 0 a n 1 0 a_0a_{n1}0 a0an10这样显然不会影响最终的结果。现在要考虑初始值边界值。显然 f 0 0 f_00 f00。最终的答案这里指的是验证中①的最小值就是 f n 1 f_{n1} fn1这样既考虑了 1 1 1 至 n n n 的所有数有没有必须选择 1 1 1 至 n n n 中某一个的限定。
验证的返回值就是最小的①是否不超过 n u m num num。
五、 编码
··
#includebits/stdc.h
#define N 110000
using namespace std;
long long f[N]{},s[N]{};
int a[N]{},q[N]{},n0,t0;
bool judge(long long num);
int main(){scanf(%d,t);while(t--){scanf(%d,n);a[0]0;s[0]0;for(int i1;in;i){scanf(%d,a[i]);s[i]s[i-1]a[i];}a[n1]0;s[n1]s[n];long long l0,rs[n]1;while(l1r){long long mid(lr)/2;if(judge(mid)false){lmid;}else{rmid;}}printf(%lld\n,r);}return 0;
}
bool judge(long long num){for(int i1;in1;i){f[i]0;}int front1,rear0;rear;q[rear]0;f[0]0;for(int i1;in1;i){while(frontrears[i-1]-s[q[front]]num){front;}f[i]f[q[front]]a[i];while(frontrearf[q[rear]]f[i]){rear--;}rear;q[rear]i;}if(f[n1]num){return true;}return false;
}
