ベスト牛フェンス二分+接頭辞と

963 ワード

テーマリンク平均値テクニック、同時にavg構想を減らす:最適問題を判定問題に変換する

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int MAX=0x3f3f3f3f;
const int N=100010;
int a[N];
double sum[N];
int n,m;
bool check(double avg){
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]-avg;
	
	double  min_a=MAX;
	for(int i=0,j=m;j<=n;i++,j++){  //i j    sum[j]-sum[i-1] ,  i 0   
		min_a=min(min_a,sum[i]);
		if(sum[j]>=min_a) return true;
		
	}
	return false;
}
int main(){

	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	double l=0,r=2000;    
	while(r-l>1e-5){
		double mid=(l+r)/2;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%d
",int(r*1000));
	return 0;
}

OkHttpの基本的な使い方

Android携帯電話のすべての短い情報を読み取る