牛客挑战赛92：D与数列

题目链接

• • 思路
  • 代码

我们先确定中位数的位置在 n u m [ n / 2 + 1 ] num[n/2+1] num[n/2+1]，然后我们除去中位数以后数列得平均值，也就是 ( b × n − a ) / ( n − 1 ) (btimes n - a)/(n-1) (b×n−a)/(n−1)，我们设它得到得值为 m m m，将其与中位数 a a a进行比较，如果他比 a a a小，那么我们就使中位数以后的数列中的值都置为 a a a，改变 a a a之前的数列的值；反之我们使中位数之前的值全部置为 a a a，改变中位数之后的值。
因为我们知道所求数列的值 x i ∈ [ 1 , n / 2 ] x_iin[1,n/2] xi​∈[1,n/2]恒小于等于 x i ∈ ( n / 2 + 1 , n ] x_iin(n/2+1,n] xi​∈(n/2+1,n]。所以对于前半部分 m a x max max为中位数，对于后半部分 m i n min min为中位数。
具体运算我们还是看代码吧。

#include
#include
#include
#include
#include
#define INF 0x7fffffff
#define ll long long
#define rei register int
using namespace std;
const int N = 1e6+5;
int n, a, b;
ll num[N];
ll sum, sum1, sum2;
void solve(){
	cin>>n>>a>>b;
	num[n/2+1] = a;
	ll m = (b*n-a)/(n-1);
	for(int i = 1;i <= n/2;i++){
		if(m > a){
			num[n/2+1-i] = a;
			num[n/2+1+i] = m+m-a;
		}
		else {
			num[n/2+1+i] = a;
			num[n/2+1-i] = m-(a-m);
		}
	}
	ll ans = b*n-m*(n-1)-a;
	if(ans<0){
		num[1] += ans;
	}
	else{
		num[n] += ans;
	}
	bool flag = true;
	for(int i = 1;i < n;i++){
		if(num[i]>num[i+1]){
			flag = false;
			break;
		}
	}
	if(!flag)cout<<-1<