1 条题解
-
0
题解:CF1918D(D. Blocking Elements)
一、 读题
1. 题目链接
(1) 洛谷链接
(2) CF链接
2. 题意简述
已知一个长度为 的数组 ,构造一个数组 (记其长度为 ),使得代价最小。代价为①和②的最大值。
$$②=\max_{0\leqslant i\leqslant m}\sum_{j=b_{i}+1}^{b_{i-1}+1}a_j $$这里,我们规定 。
二、 分析
本题 为 数量级,是标准的 题。
三、 知识
二分答案+动态规划+前缀和+单调队列优化。
四、 思路
由于本题需要同时保证两个量(①和②)最优,所以一定是确定其中一个,并用已知的这一个去求未知的。我们不难想到,可以已知②求①。这里我们利用可行性进行二分答案,即通过 函数判断在保证②最大为 的情况下能得到的最小的①是否比 小,用二分答案找到“行”与“不行”的分界点(显然②的限制越小,即可接受的最大值越大,“行”的可能性越大,这是具有单调性的)。
那么如何验证呢?
我们不难想到动态规划——定义 为考虑 中的前 个数,保证②不超过 ,并且选择了 ,在这种情况下①的最小值。
转移也不难,对于 ,我们在从 到 的范围内选择一个 ,使得从 不超过 ,这样 就可以从所有 加上 转移,当然这里是求最小值。但是遍历的代价是平方级的,所以这里用前缀和+单调队列优化。
为了方便计算和统计答案,我们定义 ,这样显然不会影响最终的结果。现在要考虑初始值(边界值)。显然,。最终的答案(这里指的是验证中①的最小值)就是 ,这样既考虑了 至 的所有数,有没有必须选择 至 中某一个的限定。
验证的返回值就是最小的①是否不超过 。
注意二分的边界是所有 相加之和,因为无论怎么选,最终的代价都是由若干个 相加(不会有重复),那么最大的①或者②都是从 加到 。
五、 代价
本题时间复杂度如下: 设 $(二分答案)·(动态规划验证)=O(log(V))·(遍历状态)·(转移)=O(log(V))·O(n)·O(1))=O(n·log(V))$,可以AC。
六、 编码
·· #include<bits/stdc++.h> #define N 110000 using namespace std; long long f[N]={},s[N]={}; int a[N]={},q[N]={},n=0,t=0; bool judge(long long num); int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); a[0]=0; s[0]=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); s[i]=s[i-1]+a[i]; } a[n+1]=0; s[n+1]=s[n]; long long l=0,r=s[n]+1; while(l+1<r){ long long mid=(l+r)/2; if(judge(mid)==false){ l=mid; }else{ r=mid; } } printf("%lld\n",r); } return 0; } bool judge(long long num){ for(int i=1;i<=n+1;i++){ f[i]=0; } int front=1,rear=0; rear++; q[rear]=0; f[0]=0; for(int i=1;i<=n+1;i++){ while(front<=rear&&s[i-1]-s[q[front]]>num){ front++; } f[i]=f[q[front]]+a[i]; while(front<=rear&&f[q[rear]]>f[i]){ rear--; } rear++; q[rear]=i; } if(f[n+1]<=num){ return true; } return false; }
- 1
信息
- ID
- 9340
- 时间
- 4000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者