P1368 均分纸牌(加强版)
题目描述
有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,纸牌总数必为 N 的倍数。可以在任一堆上取1张纸牌,然后移动。
移牌规则为:在编号为 1 堆上取的纸牌,能移到编号为 2和N 的堆上;在编号为 N 的堆上取的纸牌,能移到编号为 N-1和1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法,使每堆上纸牌数都一样多且牌的移动次数尽量少。
输入输出格式
输入格式:
第一行一个整数n
第二行为n个空格分开的正整数,为n堆纸牌的牌数。
输出格式:
只有一个数,为最少的移动次数。
输入输出样例
4
1 2 5 4
4
说明
对样例的说明:
①第4堆移动1张牌至第1堆
②第3堆移动1张牌至第2堆
③第3堆移动1张牌至第2堆
④第2堆移动1张牌至第1堆
此时移动次数为4最小
【数据范围】
对于40%的数据,n<=10000
对于100%的数据,n<=1000000,所有纸牌数总和在2147483647内
设平均数为xba
不妨设a1给了an x1 张纸牌(k可正可负),a2给了a1 x2张纸牌, a3给了a2 x3 张纸牌……an给了a(n - 1) xn张纸牌,不难发现以下方程:
xba = a1 - x1 + x2
xba = a2 - x2 + x3
xba = a3 - x3 + x4
xba = a4 - x4 + x5
......
xba = a(n - 1) - x(n - 1) + xn
xba = an - xn + x1
把他们全部相加,不难发现
nxba = a1 + a2 + a3 + .... + an
得到0 = 0
毫无用处。
我们考虑最终结果,应该是
|x1| + |x2| + |x3| + .... + |xn|
换元法,得到
ans = |x1| + |xba - a1 + x1| + |2xba -a1 - a2 + x1| + |3xba -a1 - a2 - a3 + x1| + ..... + |(n - 1)xba - Σai,i <= n - 1|转换为一次函数带绝对值的最值问题
数形结合思想,看做是数轴上点的距离。这些点是k * xba - Σai,i <= k
k应为k * xba - Σai,i <= k中的中位数
对于任意数x, x的左边就有m1个点,右边也有m2个点
x向左移动n个单位长度时,它与其他各点距离和变化为:-m1 * n + m2 * n = n(m2 - m1)
x向右移动n个单位长度时,它与其他各点距离和变化为:m1 * n - m2 * n = n(m2 - m1)
当m1 = m2时,距离和变化为0
我们看x在中位数左边一点及其以左时(m2 - m1 > 0),移动到x在中位数位置的偏移值大于零
x在中位数右边一点及其以右时(m1 - m2 > 0),移动到于x在中位数位置的偏移值大于零
因此中位数时距离和最小。
证毕
#include <bits/stdc++.h>
inline void read(long long &x){x = ;char ch = getchar();char c = ch;while(ch > '' || ch < '')c = ch, ch = getchar();while(ch <= '' && ch >= '')x = x * + ch - '', ch = getchar();if(c == '-')x = -x;}
const int INF = 0x3f3f3f3f;
const int MAXN = + ; long long n,num[MAXN],sum,f[MAXN],xba;
long long k,ans; int main()
{
read(n);
for(register long long i = ;i <= n;++ i)
{
read(num[i]);
sum += num[i];
}
xba = sum / n;
f[] = ;
for(register long long i = ;i <= n;++ i)
{
f[i] = f[i - ] + xba - num[i - ];
}
std::sort(f + , f + + n);
k = f[n/ + ];
for(long long i = ;i <= n;i ++)
{
ans += abs(k - f[i]);
}
printf("%lld", ans);
return ;
}