P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

memset函数(引用知乎上的一篇文章)

（更详细内容点击跳转）

memset简介

memset是一个初始化函数，作用是将某一块内存中的全部设置为指定的值。

void *memset(void *s, int c, size_t n);

s指向要填充的内存块。
c是要被设置的值。
n是要被设置该值的字符数。
返回类型是一个指向存储区s的指针

解题思路。

求出排列中最小的两个合并，再将其与原来的数组其他数种寻找最小进行合并，那么每次合并都是最优解，最后肯定也是最优解。

实现

我们可以用一个数组记录初始数据，再创一个新的数组来存放合并的值。
第一个数组可以直接用sort排，第二个数组本身是来记录前面合并的值，由于本身合并值就是从最小开始，所以合并值得数组肯定也是从小到大。

注意

由于我们是比较取小，所以对数组初始化要大，所以会用到memset来初始化数组，但数组初始化是从数组0开始得，如果数据习惯从数组【0】记录到数组【n】就要注意（在比较时要注意最初数组的下标值）

#include <iostream>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;
long long n, n2, a[200001], b[200001], sum = 0;
int main() {
	cin >> n;
	memset(a, 100, sizeof(a));
	memset(b, 100, sizeof(b));
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n  );
	int z = 0, x = 0, w = 0;//注意z,x的值是否为数组最初值。
	for (int i = 1; i < n; i++) {//如果你时1到n的话x,z初始就为1
		w = a[z] < b[x] ? a[z++] : b[x++];
		w += a[z] < b[x] ? a[z++] : b[x++];
		b[n2++] = w;
		sum += w;
	}
	cout << sum;
}