洛谷【P2115】[USACO14MAR]破坏Sabotage
2024-09-06 03:48:08
我对二分的理解:https://www.cnblogs.com/AKMer/p/9737477.html
题目传送门:https://www.luogu.org/problemnew/show/P2115
对于我们要求的一个“最小平均值”,我们可以通过二分来得到。对于我们二分的那个平均值,我们令每一个数全部减去它,然后这时删掉“最大子段和”就是最优策略。
假设减完平均值之后的数列和为\(sum\),那么我们二分的平均值为\(ave\),要使得平均值降到\(ave\)以下,整个数列的权值和至少要减少\(sum\)。也就是说,减得越多越好,只要能减到\(sum\)那么多,那么最低平均值必然小于等于\(ave\)。因为减完之后\(sum<=0\),也就是平均值乘以\(n\)小于等于\(ave*n\),也就是平均值会小于等于\(ave\)。
总结:如果最大子段和要大于等于删完平均值之后的数列和,那么说明我可以通过删掉这一段使得平均值降低到我们二分的值或那个值以下。
时间复杂度:\(O(nloga)\)
空间复杂度:\(O(n)\)
代码如下:
#include <cstdio>
#include <algorithm>
using namespace std;
const double eps=1e-6;
const int maxn=1e5+5;
int n;
int a[maxn];
double b[maxn],sum[maxn];
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
bool check(double ave) {
for(int i=1;i<=n;i++)
b[i]=a[i]-ave,sum[i]=sum[i-1]+b[i];//求前缀和
double mn=sum[1],fake=-1e9;//mn存1~i-1的前缀和最小值,fake存最大子段和
for(int i=2;i<n;i++) {
fake=max(fake,sum[i]-mn);//sum[i]-1~i-1的前缀和最小值就是以i结尾的最大子段和
mn=min(mn,sum[i]);//更新mn
}
if(fake>=sum[n])return 1;//判断平均值是否可以小于等于ave
return 0;
}
int main() {
n=read();double l=0,r=0;
for(int i=1;i<=n;i++)
a[i]=read(),r=max(r,(double)a[i]);
while(l+eps<r) {
double mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid;//实数二分
}
printf("%.3lf\n",r);//平均值肯定不能比r小了。
return 0;
}
最新文章
- 关于Java集合的小抄
- 配置Maven环境并创建简单的web项目步骤
- 链表栈的C语言实现
- MVC中实现只有当用户登录成功的时候才等浏览内容,否则跳转到登录页面
- 《统计推断(Statistical Inference)》读书笔记——第3章 统计分布族
- USB2.0协议笔记
- [原创]java WEB学习笔记56:Struts2学习之路---Struts 版本的 登录 demo
- [转载] 关关采集不能生成html的问题
- 一步步学习NHibernate(2)&mdash;&mdash;配置NHibernate的环境
- MongoDB:The Definitive Guide CHAPTER 2 Getting Started
- Why SignalR does not use WebSockets?
- 关于LAMP的配置之(虚拟机的安装、创建、配置)
- C语言数组之冒泡排序+折半查找法(二分查找)
- in成员资格符
- 导出excel表格,前端和后台导出
- salt+jenkins+gitlab+ecs构建公司部署平台
- windows共享文件分析
- [Luogu1891]疯狂LCM[辗转相减法]
- MacBook Apache服务
- 字符串循环右移N位