uva 11300 Spreading the Wealth 造nth_element轮子

缘起

每次 nth_element 都是直接用c++的stl（例如建kd树）很不爽, 遂想自己造一个nth_element的轮子. 毕竟还是想在有生之年多刚一些硬核代码。 遂找到了 uva 11300 Spreading the Wealth 其实算法导论第九章也讲述了nth_element的算法. 本文按照算导的思想实现一个（妈蛋，写文章的时候才发现【2】topK问题的快排解法已经按照算法导论实现过了，该算法的复杂度期望是O(n), 所以本文就不实现了）

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
题目描述：环形排列的n(n<=10^6)个人，每人有一定量的金币。每个人可以给左右相邻的两个人金币，最终使得每
个人都有相同量的金币。求被转手的最小金币数。

【输入】
首先一个n, 然后是n个人持有的金币数量.处理到文件尾

【输出】
最少易手的金币数量

样例输入：
3
100
100
100
4
1
2
5
4

样例输出：
0
4

其实与 【1】很像. 但是【1】求的是移动纸牌的次数，而这里求的是移动的纸牌数量. 但是操作方式可以模仿——都是一侧的人拿金币给自己，然后自己也拿金币给另一侧的人. 这里的金币数量可正可负（这一点和【1】一样）

令这n个人有的金币数量为a1,…,an, 均值为m, 则规定每次都是右手边的人拿金币给自己. 如上图. 则

a1-x1+x2=m

a2-x2+x3=m

…

a_{n-1}-x_{n-1}+xn=m

本来还要有一个

an-xn+x1=m的，但是不需要了，因为你把这n个方程加起来是恒等式.也就是说这个方程是可以从其他n-1个方程推导出来的.

而总共易手的金币数量是 |x1|+|x2|+…+|xn|, 而根据上面的方程将x2,…,xn 全部用x1表示得到总共易手的金币数量为

|x1|+|x1-a1+m|+|x1-(a1+a2)+2m|+…|x1-(a1+…+a_{n-1})+(n-1)*m|

令Ci=(a1+…+ai-i*m), i=1,…,n-1, C0=0， 则就是求

|x1-C0|+|x1-C1|+|x1-C2|+…+|x1-C_{n-1}|

的最小值. 而这个初中数学都学过. 只需x1取C0…C_{n-1} 这个数列的中位数即可. 而中位数算法就是本文要造的轮子——nth_element， 当然比赛的时候肯定用现成的stl. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL
#define ABS(x,y) ((x)>(y)?((x)-(y)):((y)-(x)))

typedef long long LL;
const int maxn = 1000005; // 一开始看成了10w, 结果wa了一发
LL n, a[maxn], c[maxn],ave, tot;

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%lld", &n))
	{
		tot = 0;
		for (int i = 1; i<=n; i++)
		{
			scanf("%lld", a+i);
			tot+=a[i];
		}
		ave = tot/n;
		for (int i = 1; i<n ;i++)
		{
			c[i]  =c[i-1]+a[i]-ave;
		}
		nth_element(c, c+(n-1>>1), c+n); // 则c[n-1>>1]就是中间那个
		LL ans = 0, x1 = c[n-1>>1];
		for (int i = 0;i<n; i++)
		{
			ans+=ABS(x1, c[i]);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

ac情况

Status Accepted
Time 70ms
Length 714
Lang C++11 5.3.0
Submitted 2019-09-25 08:43:14
RemoteRunId 23957763

参考

【1】https://yfsyfs.github.io/2019/09/19/sjtuoj-3016-%E5%9D%87%E5%88%86%E7%BA%B8%E7%89%8C-%E8%B4%AA%E5%BF%83/

【2】https://yfsyfs.github.io/2019/08/14/topK-%E9%9D%A2%E8%AF%95%E5%BF%85%E9%97%AE-SDUTOJ-4166-4228-%E6%95%B0%E6%8D%AE%E5%8A%A0%E5%BC%BA-%E7%AC%ACk%E5%B0%8F%E7%9A%84%E6%95%B0-%E5%A0%86%E6%8E%92-%E5%BF%AB%E6%8E%92-kth/