首页 > USACO题解 > USACO Milking Cows

USACO Milking Cows

USACO Milking Cows是一个区间合并问题,主要也就是先按开始时间从小到大排序(如果开始时间相同,结束时间也从小到大排序)。然后从头到尾合并区间。这里需要注意区间的几个问题:区间包含(测试数据里面就有这种情况)、相交等。注意对区间的更新,我的解题代码如下:

/*
	ID:stackex1
	LANG:C
	PROG:milk2
*/
#include <stdio.h>
#include <stdlib.h>

#define MAX_LEN 5010

typedef struct TagSeg
{
	int start;
	int end;
}Seg;

Seg s[MAX_LEN];

int cmp(const void *a, const void *b)
{
	Seg *sa = (Seg *)a;
	Seg *sb = (Seg *)b;
	if(sa->start == sb->start)
	{
		return sa->end > sb->end ? 1 : -1;
	}
	else
		return sa->start > sb->start ? 1 : -1;
}

int max(int a, int b)
{
	return a > b ? a : b;
}

int main(int argc, char **argv)
{
	FILE *fin = fopen("milk2.in", "r");
	FILE *fout = fopen("milk2.out", "w");
	
	int i, n, st, et, yt, nt;
	int left;
	fscanf(fin, "%d", &n);
	for(i = 0; i < n; ++i)
	{
		fscanf(fin, "%d %d", &s[i].start, &s[i].end);
	}
	qsort(s, n, sizeof(s[0]), cmp);
	nt = 0;
	i = yt = left = 0;
	while(i < n)
	{
		st = s[i].start;
		et = s[i].end;
		while(i + 1 < n && s[i + 1].start <= s[i].end)
		{
			et = max(s[i].end, s[i + 1].end);
			s[i + 1].end = et;
			++i;
		}
		if(i + 1 == n && s[i].start <= s[i - 1].end)
			et = max(s[i].end, s[i - 1].end);
		if(et - st > yt) yt = et - st;
		if(i < n - 1 && s[i + 1].start - s[i].end > nt)
			nt = s[i + 1].start - s[i].end;
		++i;
	}
	
	fprintf(fout, "%d %d\n", yt, nt);
	
	fclose(fin);
	fclose(fout);
	return 0;
}


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


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


更多



分类: USACO题解 标签: , ,
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.