欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【洛谷P1204】【USACO1.2】挤牛奶Milking Cows

程序员文章站 2022-07-12 17:32:04
...

P1204 [USACO1.2]挤牛奶Milking Cows


题目描述

三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒。第二个农民在700秒开始,在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒),而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。

你的任务是编一个程序,读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表,计算以下两点(均以秒为单位):

最长至少有一人在挤奶的时间段。

最长的无人挤奶的时间段。(从有人挤奶开始算起)

输入输出格式

输入格式:

Line 1:

一个整数N。

Lines 2..N+1:

每行两个小于1000000的非负整数,表示一个农民的开始时刻与结束时刻。

输出格式:

一行,两个整数,即题目所要求的两个答案。

输入输出样例

输入样例#1:
3
300 1000
700 1200
1500 2100
输出样例#1:
900 300

说明

题目翻译来自NOCOW。

USACO Training Section 1.2


这个题为什么我要发上来(最近一直按照难度刷USACO上的题,没怎么更),就是为了告诉自己:


想问题一定要想全!

想问题一定要想全!

想问题一定要想全!



这道题看了代码应该不难理解。

我开始落下了区间包含的情况“。


之后我发现了区间没包含,然后改了,但是还是WA。

然后下了一组数据,好像理解错了题意,应该”-1“,于是我加上了减一。

于是一直错,于是一直找不出错。


后来才发现,因为我Sublime和DEV混着用,莫名其妙两个上面文本不一样了,那一段 判断区间包含莫名其妙没了,其实根本不需要减一!!!!!


。。。浪费了我一个小时的青葱岁月


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

const int INF = 9999999;
const int MAXN = 5000 + 10;

struct 	T
{
	int start,end;
}event[MAXN];

int max1,max2;// 连续有人最长时间,连续五人最长时间
int n;

inline bool cmp(T a, T b)
{
	return a.start < b.start;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1;i <= n;i ++)
	{
		scanf("%d%d", &event[i].start, &event[i].end);
	}

	std::sort(event + 1, event + 1 + n, cmp);

	max1 = event[1].end - event[1].start;//赋初值,一是方便后面循环处理一般情况,二是防止极端数据n =1

	for(int i = 2;i <= n;i ++)  //不断比较第i和第i-1个事件
	{
		if(event[i].start <= event[i - 1].end && event[i].end <= event[i - 1].end)
		{
			event[i].end = event[i - 1].end;
			event[i].start = event[i - 1].start;
		}
		else if(event[i].start <= event[i - 1].end)
		{
			event[i].start = event[i-1].start;//将两个区间合并到一个区间
			max1 = std::max(event[i].end - event[i].start, max1);
		}
		else
		{
			max2 = std::max(event[i].start - event[i-1].end, max2);
		}

	}
	printf("%d %d", max1, max2);
	return 0;
}