Average and Median（二分）

题目传送门
其实这道题的平均数求解就是正常的求平均数的套路，但是这题有一个限制，就是相邻两个格子，必须要有一个被选中，因此我们就可以在这里跑一个dp，当前位置的状态划分可以分为，1：选，0：不选，然后对之前的状态进行转移（基础的背包问题），如果可以check函数返回yes，反之则返回no。
那么中位数在比赛的时候，没有意识到，中位数需要排序，然后选中间的较小的那个数，就没想出来，结果比赛结束幡然醒悟，其实中位数的check就是：二分出来一个中间值，check一下当前位置和中间值的大小关系，如果大于当前的mid(二分出来的当前的检索值)，我们肯定要选，小于mid的我们隔一个选一个（贪心的选最少的），
其实也不难理解，我们贪心的想，大于的我们肯定不希望错过，因为它不会影响到我们答案的值，但是小于的我们尽可能的则是能少选就少选，因为小于的会影响到我们的答案，但是要符合题目设置的规则。

#include
using namespace std;
int a[100005];
double b[100005];
double dp[100005];
int n;
int ans=0;
int st[50];
int check(double mid){
	for(int i=1;i<=n;i++){
		b[i]=(double)a[i]-mid;
	}
	dp[1]=b[1];
	dp[0]=0;
	for(int i=2;i<=n;i++){
		dp[i]=max(dp[i-1]+b[i],dp[i-2]+b[i]);
	}
	return (dp[n]>=1e-6||dp[n-1]>=1e-6);
}
double bsearch(double l,double r){
	double mid;
	while(r-l>=1e-6){
		mid=(l+r)/2;
		if(check(mid))l=mid;
		else r=mid;
	}
	return l;
}
int check2(int mid){
	int t1=0,t2=0;
	for(int i=1;i<=n;i++){
		if(a[i]>=mid)t1++;
		else{
			int j=i;
			while(j<=n&&a[j]t2;
}
int bsearch2(int l,int r){
	int mid;
	while(l>1;
		if(check2(mid))l=mid;
		else r=mid-1;
	}
	return l;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5713962.html