hdu 2993 斜率dp
2024-08-26 21:32:45
思路:直接通过斜率优化进行求解。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define Maxn 1000010
using namespace std;
__int64 sum[Maxn];
__int64 num[Maxn];
int que[Maxn*];
int main()
{
int n,k,head,rear,x;
int i,j;
double ans;
while(scanf("%d%d",&n,&k)!=EOF){
ans=;
for(i=;i<=n;i++){
scanf("%I64d",&num[i]);
sum[i]=sum[i-]+num[i];
}
head=,rear=;
que[++rear]=;
for(i=k;i<=n;i++){
j=i-k+;
while(head<rear&&(sum[i]-sum[que[head+]])*(i-que[head])>=(sum[i]-sum[que[head]])*(i-que[head+]))
head++;
ans=max(ans,(double)((double)sum[i]-(double)sum[que[head]])/(double)((double)i-(double)que[head]));
while(head<rear&&(sum[j]-sum[que[rear]])*(que[rear]-que[rear-])<=(sum[que[rear]]-sum[que[rear-]])*(j-que[rear]))
rear--;
que[++rear]=j;
}
printf("%.2lf\n",ans);
}
return ;
}
最新文章
- mysql关于排序值的问题
- 20160113第一个ANDRIOD开发日志
- SAP学习日志--RFC REMOTE FUNCTION CALL
- 3_mysql 主从复制
- 制作越狱版本的ipa文件
- 初学HTML5系列一:简单介绍
- Very Deep Convolutional Networks for Large-Scale Image Recognition
- python 自动化接口测试(6)
- WPF ListBox 获取listBoxItem
- 从零开始学习iftop流量监控(找出服务器耗费流量最多的ip和端口)
- es索引管理工具-curator
- 全栈开发工程师微信小程序 - 上
- [20181105]再论12c set feedback only.txt
- python 进程池的简单使用方法
- Codeforces510 C. Fox And Names
- C# Winfrom 发送邮件验证码&;Timer控件
- Ubuntu 16.04 源添加
- Nginx配置示例
- ats显示代理缓存
- javaweb经典面试题