洛谷P2125 题解

吐槽：

只能说这道题很数学，本数学蒟蒻推了半天没推出来，只知道要用绝对值，幸亏教练提醒，才勉强想出正解（似乎不是这样的），真的是很无语。

以上皆为吐槽本题，可直接跳过

分析：

既然题目是要使书架上的书一样多，那么就一定要求平均数了

$s=\sum_{i=1}^n book_i,s=s\div n$，$s$即为平均数
继续分析，我们将平均数减掉，得出一个书架需要改变的量$x_1,x_2,$···$x_n$,这时我们发现，我们可以得出一个方程组

$\begin{cases}x_1=a_1-a_n\\x_2=a_2-a_1 \\x_3=a_3-a_2\\\cdots\\x_n=a_n-a_{n-1}\end{cases}$

$\Longrightarrow $

$\begin{cases}a_1=x_1+a_n\\a_2=x_2+a_1 \\a_3=x_3+a_2\\\cdots\\a_n=x_n+a_{n-1}\end{cases}$

(其中$a_i$($i\in N^+$)为SY从$i$书架向下一个书架抱$a_i$本书）

我们惊喜的发现，我们得出了这样一个方程组 $\begin{cases} a_1=x_1+a_n\\ a_2=x_2+x_1+a_n\\ a_3=x_3+x_2+x_1+a_n\\ \cdots\\a_n=x_n+x_{n-1}+\cdots+x_1+a_n\end{cases}$
得出以上方程之后，继续观察，发现第一问：SY最少抱多少本书，即求$sum=\sum_{i=1}^n \left | a_i \right |$的最小值($\left | a_i \right |$表示数$a_i$的绝对值)

得：$sum= \left |y_1+a_n \right |+\left | y_2+a_n \right |+\left | y_3+a_n \right |+\cdots+\left | y_n+a_n \right |$

$\because n \in E$($E$表示奇数集)

$\therefore$当$a_n=y_k$(其中$k=\frac{n}{2}+1$)时，$sum$有最小值。

第一问迎刃而解~~~
剩下的便变得简单起来

因为我们$a_i$设的是SY从$i$书架抱到到下一个书架的书籍

所以SY从$i$书架抱到到上一个书架的书籍为$-a_{i-1}$

部分代码

1.前缀和：

用于求$y_i$

for(LL i=1;i<=n;i++)

{

	sum[i]=sum[i-1]+book[i]-s; //前缀和标准写法

}

2.中位数：

用于求$a_n$

这里有两种方法：

法一：排序+查找（时间代价：总程序32ms）

sort(sum+1,sum+n+1);

LL mid=sum[n/2+1];//中位数

法二：nth_element（c++自带函数库，时间代价：总程序12ms）

nth_element(sum+1,sum+n/2+1,sum+n+1);

LL mid=sum[n/2+1];//更快的中位数求法

综上，nth_element要快很多,我的名字果然牛逼

具体用法：nth_element(头位置，中位数位置，尾位置);

好吧，这道题数学分析很难，但代码确实很简单，比AC自动机，FFT，那些好多了

给你一个假代码（逃

#include<bits/stdc++.h>

#define LL long long

#define Maxn 5000011

#define QwQ 1

#define QAQ 0

using namespace std;

int n;

LL book[Maxn];

LL s=0;

LL sum[Maxn];

LL s2=0;

LL veb[Maxn];

int main()

{

	cin>>n;

	for(LL i=1;i<=n;i++)

	{

		scanf("%lld",&book[i]);

		s+=book[i];

	}

	s/=n;//平均数

	for(LL i=1;i<=n;i++)

	{

		sum[i]=sum[i-1]+book[i]-s;

		book[i]=sum[i];

	}

	sort(sum+1,sum+n+1);

	LL mid=sum[n/2+1];//中位数

	/*

	nth_element(sum+1,sum+n/2+1,sum+n+1);

	LL mid=sum[n/2+1];更快的中位数求法

	*/

	for(LL i=1;i<=n;i++)

	{

		s2+=abs(sum[i]-mid);

		veb[i]=book[i]-mid;

	}

	printf("%lld\n",s2);

	printf("%lld %lld\n",-veb[n],veb[1]);

	for(LL i=2;i<=n;i++)

	{

		printf("%lld %lld\n",-veb[i-1],veb[i]);

	}

	return mid==0?max(QwQ,QAQ):0;

}

巴特西

洛谷P2125 题解

吐槽：

分析：

部分代码

1.前缀和：

2.中位数：

给你一个假代码（逃

最新文章

热门文章