寒假集訓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('
');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
新豐美酒鬥十千，鹹陽遊俠多少年！