22-07-14 personal training match 2 competition experience

Most of the valley questions , except J and L Are segment trees and dp 

Too lazy to paste the intranet address .

 A,B: Water problem

C: Thinking greedy （ Can't think of , It feels a little abstract ）

D: A binary prefix and variant , A little difficult

E:dfs

F: Complex simulation graphics

H: simulation

K: water

L: Line segment tree

J: A line of pressure dp But I'm not very good at solving problems （）

Catalog

D:PROSJEK

---

D:PROSJEK

Sample Input

6 3

7 1 2 1 3 6

Sample Output

3.333333

This question is very good , Finally, a binary variant is achieved , I always feel that I only know the surface of the routine

check Time complexity O(n).

Ideas ： Accuracy dichotomy + Take with ruler （ Average thinking ）+ The prefix and

The essence is after two points , It becomes the problem of whether the average is known and satisfied , Just take it with a ruler , And originally it can't be made with a ruler （ I'd like to think twice , Chi take also wanted to , But we didn't think together doge）

#include <bits/stdc++.h>
//#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
#define pii pair<int,int>
using namespace std;
const int N=3e5+5;
const double eps=1e-3;
double d[N];
int a[N];
double p[N];
int n,k;
bool check(double x){
	rep(i,1,n) p[i]=p[i-1]+a[i]-x;
	double mi=0;
	rep(i,k,n){
		if (p[i]>=mi) return true;
		mi=min(mi,p[i-k+1]);
	}
	return false;
}
void work(){
	cin>>n>>k;
	rep(i,1,n){
		cin>>a[i];
	}
	double l=0,r=1000010,mid;
	while (abs(l-r)>eps){
		mid=1.0*(l+r)/2;
		if (check(mid)==false){
			r=mid;
		}
		else{
			l=mid;
		}
	}
	printf("%.6lf",mid);
	
}
signed main(){
	CIO;
	work();
	return 0;
}

This time, all the other topics are covered by this D masked （ In fact, I am too lazy to write , And understand DP Well ）