题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2993

题目大意:给出n,k,给定一个长度为n的序列,从其中找连续的长度大于等于k的子序列使得子序列中的平均值最小。

解题思路:斜率DP经典题,

详细分析见:
还有要注意要用输入输出外挂,不是getchar()版的,是fread()版的,第一次遇到这么变态的题目- -|||。
代码:
 #include<iostream>
#include<cstring>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int N=1e5+; int q[N],head,tail;
long long sum[N]; double Slope(int k,int j){
return double(sum[j]-sum[k])/(j-k);
}
//输入输出外挂
const int BUF=;
char Buf[BUF],*buf=Buf;
template <class T>
inline void read(T &a){
for(a=;*buf<;buf++);
while(*buf>)
a=a*+*buf++-;
} int main(){
int n,k;
int tot=fread(Buf,,BUF,stdin);
while(){
if(buf-Buf+>=tot)break;
read(n),read(k);
for(int i=;i<=n;i++){
read(sum[i]);
sum[i]+=sum[i-];
}
double ans=;
head=tail=;
q[tail++]=;
for(int i=k;i<=n;i++){
while(head+<tail&&Slope(q[head],i)<=Slope(q[head+],i)){
head++;
}
ans=max(ans,Slope(q[head],i));
int j=i-k+;
while(head+<tail&&Slope(q[tail-],q[tail-])>=Slope(q[tail-],j)){
tail--;
}
q[tail++]=j;
}
printf("%.2f\n",ans);
}
return ;
}
 
05-04 05:01