Barn Repair

/*
ID: fykalv3
LANG: C
TASK: barn1
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp(const void *a, const void *b)
{
	return *(int *)a - *(int *)b;
}

int main()
{
	FILE *fin = fopen("barn1.in", "r");
	FILE *fout = fopen("barn1.out", "w");
	int m, s, c, i, j, sum;
	int num[400], run[400];
	fscanf(fin, "%d %d %d", &m, &s, &c);
	if (m >= c)
		fprintf(fout, "%d\n", c);
	else {
		for (i = 0; i < c; i++)
			fscanf(fin, "%d", &num[i]);
		qsort(num, c, sizeof(num[0]), cmp);
		for (i = 0; i < c-1; i++) {
			run[i] = num[i+1] - num[i];
		}
		qsort(run, c-1, sizeof(run[0]), cmp);
		sum = 0;
		for (i = 0; i < c-m; i++) 
			sum += run[i];
		fprintf(fout, "%d\n", sum+m);
	}
	fclose(fin);
	fclose(fout);
	return 0;
}

贪心算法，计算出来距离最大的m-1个间隔然后都相加就ok了，其中要注意的就是if那个判断语句