寒假集训day1学了...二分？三分？
都有吧，例题还是挺难的觉得，如果没见过的话...
这道题呢 嗯二分我也想到了 二分 答案吧 长度
wn dalao直接说这O(n)扫一遍不就完了么，贪心...
然后冰粉那么简单 |ai|<=1e9; 这个有可能是负值那么 就形成了贪？贪不了的结果。
原因 自己脑补吧 非常显然。
那么我们二分答案 二分完以后还有细节，这个地方我出现失误想错了。（当然也是比较amazing的！）
我想的是搞前缀和然后 只管当前到达 i 和 (i-m)直接的和其实并不是。因为 负值的影响。
我们只能...
这样才能完美验证成功！
这个理解起来并不困难，还有下一道题.
这个就比较难想了，至少我想了20min还没有check的思路 。（这个英语较简单我大致能看懂了）
求一个平均值最大且合法的序列，首先我们并不知道 平均值是多少，当然也不知道这个序列有多长。
我们在合法的序列中找平均值最大的不就好了么。 那么顺理成章二分答案 平均值。
check 呢？好难啊 咋么写复杂度都会高且不好写。
那么此时我们可以将整个序列-mid 然后取前缀和 然后重复上个题目就行了，区别在于这次我们要维护这个字段>=0;
wa 到 家了 很迷 我也很迷 ，各种wa 谁知道哪错了！
首先是输出的时候 l 和 r 取哪个？ 发现样例都不好过。
问过学长后是 int 向下取整 printf %,lf 四舍五入 也就是 perform rounding
输出 l 还是 r l不行啊 int(l*1000)==6499 咋么搞得？我check 一下r？能输出r 就输出r？
但是精度在放那 我想check 效果不大。此时 int(r*1000)=6500
直接输出r 即可 因为r向下取整那不就是答案了么。
值得注意的是 这道题范围出错了 0=<ncows<=2000;真的是让我wa到怀疑人生了！
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<iomanip> #include<cstring> #include<string> #include<cstdlib> #include<cmath> #include<algorithm> #include<cctype> #include<utility> #include<set> #include<bitset> #include<queue> #include<stack> #include<deque> #include<map> #include<vector> #include<ctime> #define INF 2147483646 using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void put(int x) { x<0?putchar('-'),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar('\n');return; } const int MAXN=100002; int n,m; int a[MAXN],maxx=0; double b[MAXN]; double min(double x,double y) { return (x-y)>=0.00000000000001?y:x; } double max(double x,double y) { return (x-y)>=0.00000000000001?x:y; } int check(double x) { double minn=INF,maxx=-INF; for(int i=1;i<=n;i++) { b[i]=(double)a[i]-x; b[i]+=b[i-1]; } for(int i=1;i<=n;i++) { if(i>=m)minn=min(minn,b[i-m]); maxx=max(maxx,b[i]-minn); } if(maxx>=0.0000000)return 1; return 0; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=n;i++) { a[i]=read(); if(a[i]>maxx)maxx=a[i]; } double l=0,r=maxx; while(l+0.00001<r) { double mid=(l+r)/2; if(check(mid)==1)l=mid; else r=mid; } put(r*1000); return 0; } View Code新丰美酒斗十千，咸阳游侠多少年！
转载于:https://www.cnblogs.com/chdy/p/10374170.html
