Average and Median(二分)

Average and Median(二分),第1张

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

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-18

发表评论

登录后才能评论

评论列表(0条)

保存