Codeforces Round #619 (Div2) B. Motarack's Birthday

Myth丶恋晨 2023-07-06 08:47 47阅读 0赞

[B. Motarack’s Birthday][B. Motarack_s Birthday]

题意：给你一个数组，这个数组有消失的数（所有消失数都相等），让你求消失数k使整个数组中相邻两个数绝对值的最大值最小。

比赛时错误思路：把所有非消失数累加，除以非消失数的个数，这个平均值就是消失数，这是错误的。

错误原因：可能非消失数很大，但是这几个连续的非消失数相邻两个的绝对值很小，你把非消失数的平均数置为消失数的值，可能会让数组相邻之间的绝对值变大，不是最优的。

比如： -1 1 2 3 4 5 正确答案消失数为0或1或2 绝对值最大值为1  
错误解法，1-5平均数为3 数组为3 1 2 3 4 5 消失数为3，绝对值最大值为2，显然不对。

## 正解： ##

我们只需要更新-1前后相邻的数的最大值和最小值。消失数的值就是（最大值+最小值）/ 2，不要取-1相邻的数和的平均值，这样绝对值的最大值可能不是最优的（1 -1 10 -1 10 -1 10 -1 10 ；（最大值+最小值）/ 2 的 k为5，为最优的k；如果平均数的话k是8，不是最优答案） ;  
这样做的话，我们可以保证-1相邻的前后两个数绝对值的最大值是最小的。  
最后统计整个数组的绝对值的最大值了。

#include<iostream>
    #include<cstring> 
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn=1e6+10;
    ll a[maxn];
    void init(ll n)
    { 
    	for(int i=0;i<=n+1;i++)
    		a[i]=-1;
    }
    int main()
    { 
    	ll t;
    	cin>>t;
    	while(t--)
    	{ 
    		ll n,num=0;
    		cin>>n;
    		init(n);
    		for(int i=1;i<=n;i++)
    		{ 
    			cin>>a[i];
    			if(a[i]==-1) num++;
    		}
    		if(num==n)
    			cout<<"0 0"<<endl;
    		else
    		{ 
    			ll mx=-1,mi=0x3f3f3f3f;
    			for(int i=1;i<=n;i++)
    			{ 
    				if(a[i]==-1&&a[i-1]!=-1)
    				{ 
    					mx=max(mx,a[i-1]);
    					mi=min(mi,a[i-1]);
    				}
    				if(a[i]==-1&&a[i+1]!=-1)
    				{ 
    					mx=max(mx,a[i+1]);
    					mi=min(mi,a[i+1]);
    				}
    			} 	
    			ll ave=(mx+mi)>>1;
    			ll jd=0;
    			if(a[1]==-1) a[1]=ave;
    			for(int i=2;i<=n;i++)
    			{ 
    				if(a[i]==-1) a[i]=ave;
    				jd=max(jd,abs(a[i]-a[i-1]));
    			}
    			cout<<jd<<" "<<ave<<endl;
    		}	
    	}
    	return 0;
    }

[B. Motarack_s Birthday]: http://codeforces.com/contest/1301/problem/B