首页 > USACO题解 > USACO Barn Repair

USACO Barn Repair

贪心问题。首先可以按照stall的编号从小到大排序,然后计算每个stall编号之见的距离,再按照距离从大到小排序(也可以从小到大,反正排序就行了),然后找出M-1个最大的距离,这些都是分隔段,其他的stall都是应该被覆盖的。

比如,1 3 9,给一个board的话,肯定是全部覆盖;如果能给两个board,则是一个覆盖1,2,3;另一个覆盖9。题目大概就是这个意思:

/*
	ID:stackex1
	LANG:C
	PROG:barn1
*/
#include <stdio.h>
#include <stdlib.h>
 
#define MAX_LEN 512
 
int cmp(const void *pa, const void *pb)
{
	return *(int*)(pa) > *(int*)(pb) ? 1 : -1;
}
 
int main(int argc, char **argv)
{
	FILE* fin = fopen("barn1.in", "r");
	FILE* fout = fopen("barn1.out", "w");
 
	int i, m, s, c, res;
	int diff[MAX_LEN], src[MAX_LEN];
 
	fscanf(fin, "%d %d %d", &m, &s, &c);
	for(i = 0; i < c; ++i)
		fscanf(fin, "%d", &src[i]);
	qsort(src, c, sizeof(src[0]), cmp);
	for(i = 0; i < c-1; ++i)
		diff[i] = src[i+1] - src[i];
	qsort(diff, c-1, sizeof(diff[0]), cmp);
	res = src[c-1] - src[0] + 1;
	for(i = c-2; i >= 0 && m > 1; --i, --m)
		res -= (diff[i] - 1);
	fprintf(fout, "%d\n", res);
	fclose(fin);
	fclose(fout);
 
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> USACO Barn Repair
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: USACO题解 标签: ,
  1. 2010年11月30日23:13 | #1

    看来你很喜欢研究算法,呵呵

    [回复]

  2. 2010年12月1日12:15 | #2

    @winson
    主要是为了竞赛,然后就是在这个过程中提升自己。呵呵

    [回复]

  3. 2011年11月16日17:22 | #3

    站長您這份code簡潔又給力,推一個。

    [回复]

    代码疯子 回复:

    @N.C, 呵呵,好久沒有做USACO了,大學做了一段時間,現在要畢業了,不關注這方面了。

    [回复]

  4. zkx06111
    2014年2月13日16:36 | #4

    cmp可以直接写成return *(int*)(pa) > *(int*)(pb);

    [回复]