hdu2993之斜率dp+二分查找

时间：2021-12-22 03:27:29

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;

}

相关文章