Barn Repair

kalviny

/*ID: fykalv3LANG: CTASK: 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那个判断语句