首页 > 其他 > 详细

HDU 2993 MAX Average Problem(斜率DP经典+输入输出外挂)

时间:2017-11-09 23:56:51      阅读:347      评论:0      收藏:0      [点我收藏+]

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

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

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

详细分析见:
还有要注意要用输入输出外挂,不是getchar()版的,是fread()版的,第一次遇到这么变态的题目- -|||。
代码:
 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<stdio.h>
 5 using namespace std;
 6 const int N=1e5+5;
 7 
 8 int q[N],head,tail;
 9 long long sum[N];
10 
11 double Slope(int k,int j){
12     return double(sum[j]-sum[k])/(j-k);
13 }
14 //输入输出外挂 
15 const int BUF=25000000;
16 char Buf[BUF],*buf=Buf;
17 template <class T>
18 inline void read(T &a){
19     for(a=0;*buf<48;buf++);
20     while(*buf>47)
21         a=a*10+*buf++-48;
22 }
23 
24 int main(){
25     int n,k;
26     int tot=fread(Buf,1,BUF,stdin);
27     while(1){
28         if(buf-Buf+1>=tot)break;
29         read(n),read(k);
30         for(int i=1;i<=n;i++){
31             read(sum[i]);
32             sum[i]+=sum[i-1];
33         }
34         double ans=0;
35         head=tail=0;
36         q[tail++]=0;
37         for(int i=k;i<=n;i++){
38             while(head+1<tail&&Slope(q[head],i)<=Slope(q[head+1],i)){
39                 head++;
40             }
41             ans=max(ans,Slope(q[head],i));
42             int j=i-k+1;
43             while(head+1<tail&&Slope(q[tail-2],q[tail-1])>=Slope(q[tail-1],j)){
44                 tail--;
45             }
46             q[tail++]=j;
47         }
48         printf("%.2f\n",ans);
49     }
50     return 0;
51 }

 

 

 

HDU 2993 MAX Average Problem(斜率DP经典+输入输出外挂)

原文:http://www.cnblogs.com/fu3638/p/7811903.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!