2803. The Max

题目意思很简单，不说了，第一反应就是先进行排序，还要注意数据的范围是大于int的，所以要用long long。

于是乎就想利用这个题目练练排序算法，目前只有快排、堆排。

Example:

Input:

2

1 2

Output:

4017

Note:

Each test case contains a single integer N (1<=N<=100).

The next line contains N integers, meaning the value of V1, V2….Vn.(1<= Vi <=10^8).

The input is terminated by a set starting with N = 0. This set should not be processed..

新知识:

_msize(a) / sizeof(LL)可以获取动态数组的长度，以后面试的时候被问到数组长度未知，就可以秀了。

快速排序思路很简单，但是要注意判断边界情况，按照严蔚敏书上的思路，一定是相等的时候跳出循环。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/*
 *严蔚敏数据结构书上的快速排序
 */
int Partition(LL* a,int low,int high)
{
	LL pivot = a[low];
	while (low < high){
		while (low < high&&a[high] > pivot)--high;
		a[low] = a[high];
		while (low < high&&a[low] < pivot)++low;
		a[high] = a[low];
	}
	a[low] = pivot;
	return low;
}
void QSort(LL* a, int low, int high)
{
	if (low < high){
		int pivotloc = Partition(a, low, high);
		QSort(a, low, pivotloc - 1);
		QSort(a, pivotloc + 1, high);
	}
}
void QuickSort(LL* a)
{
	int len = _msize(a) / sizeof(LL);//稍微自己改了一下
	QSort(a, 0, len - 1);
}
/*
 * 自己写的快速排序，其实是按照严蔚敏书上的思路来的，所以代码结构很相似
 */
void QuickSort(LL* a,int len)
{
	if (len <= 1)
		return;
	LL pivot = a[0];
	int le = 0, ri = len - 1;
	while (le<ri){
		while (le < ri&&a[ri] >= pivot){
			ri--;
		}
		a[le] = a[ri];
		while (le < ri&&a[le] <= pivot){
			le++;
		}
		a[ri] = a[le];
	}
	a[le] = pivot;
	QuickSort(a, le);
	QuickSort(a + le + 1, len - le - 1);
}
/*
 * 自己写的堆排，注意每次更新堆之后需要把根节点与换到数组后面去，然后更新的时候就不把它算进来。直至遍历到根节点
 */
void Up2Down(int e, LL* a)
{
	int len = a[0];
	int le = 2 * e;
	int ri = 2 * e + 1;
	int position;
	if (le > len)
		return;
	if (ri > len){
		position = le;
	}
	else{
		position = a[le] > a[ri] ? le : ri;
	}
	if (a[position] > a[e]){
		LL tmp = a[e];
		a[e] = a[position];
		a[position] = tmp;
		Up2Down(position, a);
	}
}
void HeapSort(LL* a)
{
	int len = a[0];
	//叶子结点就不算了,自底向上更新
	for (int i = len / 2; i >= 1; i--){
		Up2Down(i, a);
	}
	for (int i = len; i > 1; i--){
		int tmp = a[1];
		a[1] = a[i];
		a[i] = tmp;
		a[0] = i - 1;
		Up2Down(1, a);
	}
}