Two point answer, 01 score planning (mean / median conversion), DP

Topic link
Solution to the problem

Add ：

1. About the average 01 Planning understanding ：

$$\frac{\sum a_i}{n}\ge mid$$

$$\frac{\sum a_i}{{\sum }_{i=1}^{n}1}\ge mid$$

$$\sum (a_i-mid)\ge 0$$

2. Also note that the median is an integer , The average is a floating point number
3. We know that for a certain location $i$, You can choose this number , You can also choose his next number , Subconsciously want to use DFS, But the data is too big , Today I know I can use DP Before dynamic planning is selected $i$ The maximum number .
4. DP Thinking from “ From which position does a certain position move ” consider , The array represents the pre selection $i$ The maximum number .

#include<iostream>
using namespace std;
const int N=1e5+100;
double a[N],b[N],dp[N][2];
int n;
bool check1(double mid)
{
    
	for(int i=1;i<=n;i++) b[i]=a[i]-mid;
	
	for(int i=1;i<=n;i++)
	{
    
		dp[i][0]=dp[i-1][1];
		dp[i][1]=max(dp[i-1][1],dp[i-1][0])+b[i];		
	}
	
	return max(dp[n][0],dp[n][1])>=0;
}
bool check2(int mid)
{
    
	for(int i=1;i<=n;i++) b[i]=(a[i]>=mid)? 1:-1;
	
	for(int i=1;i<=n;i++)
	{
    
		dp[i][0]=dp[i-1][1];
		dp[i][1]=max(dp[i-1][1],dp[i-1][0])+b[i];		
	}
	
	return max(dp[n][0],dp[n][1])>0;
}
int f2()
{
    
	int l=0,r=0x3f3f3f3f; // The median of two 
	while(l<r)
	{
    
		int mid=(l+r+1)/2;
		if(check2(mid)) l=mid;
		else r=mid-1;
	}
	return l;
}
double f1()	// Two point average 
{
    
	double l=0,r=0x3f3f3f3f;
	while(r-l>1e-6)
	{
    
		double mid=(l+r)/2;
		if(check1(mid)) l=mid;
		else r=mid;
	}
	
	return l;
}
int main()
{
    
	cin>>n;
	for(int i=1;i<=n;i++) 
		cin>>a[i];
	
	cout<<f1()<<endl<<f2()<<endl;
	return 0;
}