【POJ 2018】 Best Cow Fences
2024-08-31 00:49:34
【题目链接】
http://poj.org/problem?id=2018
【算法】
二分平均值
检验时将每个数减去二分的值,求长度至少为L的子序列和的最大值,判断是否大于0
【代码】
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <stack>
#include <limits.h>
using namespace std;
#define MAXN 100010
const double eps = 1e-; int n,f,i;
double a[MAXN],b[MAXN],s[MAXN];
double l,r,mid,ans; inline bool check(double x)
{
int i;
double mn = 1e6,ret = -1e6;
for (i = ; i <= n; i++) b[i] = a[i] - x;
for (i = ; i <= n; i++) s[i] = s[i-] + b[i];
for (i = f; i <= n; i++)
{
mn = min(mn,s[i-f]);
ret = max(ret,s[i]-mn);
}
return ret >= ;
} int main() { scanf("%d%d",&n,&f);
for (i = ; i <= n; i++) scanf("%lf",&a[i]);
l = -1e6; r = 1e6;
while (r - l > eps)
{
mid = (l + r) / ;
if (check(mid)) l = mid;
else r = mid;
}
printf("%d\n",int(r*)); return ; }
最新文章
- 批量创建10个用户stu01-stu10
- 磁盘阵列(RAID)实例
- TCP/IP各层主要功能
- Selenium2Library系列 keywords 之 _ElementKeywords
- cicm0804吊起
- 【HDOJ】1688 Sightseeing
- wcf ServiceContract
- 多线程爬坑之路--并发,并行,synchonrized同步的用法
- MySQL监听数据库存储过程出现异常
- Python教程(2.1)——控制台输入
- MySQL实战45讲学习笔记:索引(第四讲)
- apache做反向代理
- Laravel API Tutorial: How to Build and Test a RESTful API
- Servlet工作原理解析
- 2019年微服务5大趋势,你pick哪个?
- Freemarker list 的简单使用
- 频分复用(Frequency Division Multiplexer)
- 《Linux内核设计与实现》第3章读书笔记
- django知识点回顾与补充
- 如何优雅的编写Objective-C语言?
热门文章
- nginx报错:Permission denied
- 在添加新内容时,creatat没有数据
- 【Redis】四、Redis设计原理及相关问题
- error: Bean property &#39;userDAO&#39; is not writable or has an invalid setter method.
- 向appstore提交app流程
- 浅谈AC自动机模板
- 用php生成HTML文件的类
- Codeforces 938C - Constructing Tests
- [bzoj2141][排队] (分块大法好)
- linux常用命令大全(linux基础命令+命令备忘录+面试复习)