MAX Average Problem

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 5825    Accepted Submission(s): 1446

Problem Description
Consider a simple sequence which only contains positive integers as a1, a2 ... an, and a number k. Define ave(i,j) as the average value of the sub sequence ai ... aj, i<=j. Let’s calculate max(ave(i,j)), 1<=i<=j-k+1<=n.
 
Input
There multiple test cases in the input, each test case contains two lines.

The first line has two integers, N and k (k<=N<=10^5).

The second line has N integers, a1, a2 ... an. All numbers are ranged in [1, 2000].
 
Output
For every test case, output one single line contains a real number, which is mentioned in the description, accurate to 0.01.
 
Sample Input
10 6
6 4 2 10 3 8 5 9 4 1
 
Sample Output
6.50

參考:kuangbin--hdu2993

直接斜率DP:O(N)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std; const int MAX=100000+10;
int n,k;
int s[MAX],q[MAX];
double dp[MAX],sum[MAX]; double GetY(int i,int j){
return sum[i]-sum[j];
} int GetX(int i,int j){
return i-j;
} double DP(){
int head=0,tail=1;
q[head]=0;
double ans=0;
for(int i=1;i<=n;++i)sum[i]=sum[i-1]+s[i]*1.0;
for(int i=k;i<=n;++i){
int j=i-k;
while(head+1<tail && GetY(j,q[tail-1])*GetX(q[tail-1],q[tail-2])<=GetY(q[tail-1],q[tail-2])*GetX(j,q[tail-1]))--tail;
q[tail++]=j;
while(head+1<tail && GetY(i,q[head])*GetX(i,q[head+1])<=GetY(i,q[head+1])*GetX(i,q[head]))++head;
dp[i]=(sum[i]-sum[q[head]])/(i-q[head]);
ans=max(ans,dp[i]);
}
return ans;
} int input(){//加速外挂
char ch=' ';
int num=0;
while(ch<'0' || ch>'9')ch=getchar();
while(ch>='0' && ch<='9')num=num*10+ch-'0',ch=getchar();
return num;
} int main(){
while(~scanf("%d%d",&n,&k)){
for(int i=1;i<=n;++i)s[i]=input();
printf("%0.2lf\n",DP());
}
return 0;
} 斜率DP+二分查找:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std; const int MAX=100000+10;
int n,k;
int s[MAX],q[MAX];
LL sum[MAX]; LL GetY(int i,int j){
return sum[i]-sum[j];
} int GetX(int i,int j){
return i-j;
} LL check(int mid,int i){
return GetY(i,q[mid+1])*GetX(q[mid+1],q[mid])-GetY(q[mid+1],q[mid])*GetX(i,q[mid+1]);
} int search(int l,int r,int i){
//由于斜率单调递增
/*int top=r;
while(l<=r){//依据i与mid的斜率 和 i与mid+1的斜率之差求切点
if(l == r && l == top)return q[l];//这里一定要注意假设切点是最后一个点须要另判,由于mid+1不存在会出错
int mid=(l+r)>>1;
if(check(mid,i)<0)r=mid-1;
else l=mid+1;
}*/
while(l<r){//依据i与mid的斜率 和 i与mid+1的斜率之差求切点
int mid=(l+r)>>1;
if(check(mid,i)<0)r=mid;
else l=mid+1;
}
return q[l];
} double DP(){
int head=0,tail=1,p;
q[head]=0;
double ans=0,dp;
for(int i=1;i<=n;++i)sum[i]=sum[i-1]+s[i];
for(int i=k;i<=n;++i){
int j=i-k;
while(head+1<tail && GetY(j,q[tail-1])*GetX(q[tail-1],q[tail-2])<=GetY(q[tail-1],q[tail-2])*GetX(j,q[tail-1]))--tail;
q[tail++]=j;
p=search(head,tail-1,i);//依据相邻点与i点的斜率之差二分查找切点
dp=(sum[i]-sum[p])*1.0/(i-p);
if(dp>ans)ans=dp;
}
return ans;
} int input(){//加速外挂
char ch=' ';
int num=0;
while(ch<'0' || ch>'9')ch=getchar();
while(ch>='0' && ch<='9')num=num*10+ch-'0',ch=getchar();
return num;
} int main(){
while(~scanf("%d%d",&n,&k)){
for(int i=1;i<=n;++i)s[i]=input();
printf("%0.2lf\n",DP());
}
return 0;
}

最新文章

  1. Xamarin的不归路-生成安卓错误2
  2. github desktop 在线安装失败解决方案
  3. Tomcat 5.5启动需要用户名密码的解决方案
  4. linux查看某个端口被占用
  5. C#中的 具名参数 和 可选参数
  6. 在线最优化求解(Online Optimization)之一:预备篇
  7. C#...何时需要重写ToString()方法?
  8. java设计模式--结构型模式--享元模式
  9. Android 仿微信滑动删除
  10. PendingIntent详解
  11. 人工智能(AI)库TensorFlow 踩坑日记之一
  12. oracle 字符串分割函数
  13. LinkedHashSet 元素唯一,存储取出有序
  14. [hihoCoder] #1096 : Divided Product
  15. 【Android】21.2 2D图形图像处理(Canvas和Paint)
  16. ubuntu 命令 dpkg -l
  17. 站点下的robots
  18. mysql 分区 限制
  19. Python 串口通信 GUI 开发
  20. leetcode-位1的个数(位与运算)

热门文章

  1. 使用函数指针和多态代替冗长的if-else或者switch-case
  2. The mmap module
  3. Urxvt - awesome
  4. cocos2d 走动椭圆
  5. 在gem5的full system下运行 alpha编译的测试程序 running gem5 on ubuntu in full system mode in alpha
  6. 通过Camera进行拍照
  7. Linux IO 调度器
  8. 最锋利的Visual Studio Web开发工具扩展:Web Essentials详解
  9. NLP 苏图南 打破自我设限 突破自我—在线播放—优酷网,视频高清在线观看
  10. ZooKeeper场景实践:(2)集中式配置管理