吐槽：
只能说这道题很数学，本数学蒟蒻推了半天没推出来，只知道要用绝对值，幸亏教练提醒，才勉强想出正解（似乎不是这样的），真的是很无语。
以上皆为吐槽本题，可直接 跳过
分析：
-
既然题目是要使书架上的书一样多，那么就一定要求平均数了
(s=sum_{i=1}^n book_i,s=sdiv n)，(s)即为平均数 -
继续分析，我们将平均数减掉，得出一个书架需要改变的量(x_1,x_2,)···(x_n),这时我们发现，我们可以得出一个方程组
(egin{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 $
(egin{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)((iin N^+))为SY从(i)书架向下一个书架抱(a_i)本书）我们惊喜的发现，我们得出了这样一个方程组 (egin{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_nend{cases})
-
得出以上方程之后，继续观察，发现第一问：SY最少抱多少本书，即求(sum=sum_{i=1}^n left | a_i ight |)的最小值((left | a_i ight |)表示数(a_i)的绝对值)
得：(sum= left |y_1+a_n ight |+left | y_2+a_n ight |+left | y_3+a_n ight |+cdots+left | y_n+a_n ight |)(ecause n in E)((E)表示奇数集)
( herefore)当(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
",s2);
printf("%lld %lld
",-veb[n],veb[1]);
for(LL i=2;i<=n;i++)
{
printf("%lld %lld
",-veb[i-1],veb[i]);
}
return mid==0?max(QwQ,QAQ):0;
}