CUMTOJ:algorithm-法师康的工人(题解)

题目描述:

三个法师康的工人每天早上6点到工厂开始到三条产品生产线上组装桔子手机。第一个工人在200时刻开始(从6点开始计时,以秒作为单位)在生产线上开始生产,一直到1000时刻。第二个工人,在700时刻开始,在1100时刻结束。第三个工人从1500时刻工作到2100时刻。期间最长至少有一个工人在生产线上工作的连续时间为900秒(从200时刻到1100时刻),而最长的无人生产的连续时间(从生产开始到生产结束)为400时刻(1100时刻到1500时刻)。 

你的任务是用一个程序衡量N个工人在N条产品线上的工作时间列表(1≤N≤5000,以秒为单位)。 

·最长的至少有一个工人在工作的时间段 

·最长的无人工作的时间段(从有人工作开始计) 

输入

输入第1行为一个整数N,第2-N+1行每行包括两个均小于1000000的非负整数数据,表示其中一个工人的生产开始时间与结束时间。

输出

输出为一行,用空格分隔开两个我们所求的数。

样例输入

3
200 1000
700 1100
1500 2100

样例输出

900 400

算法描述

本题可归结为寻找连续区间的最大值,使用滑动窗口较为方便。

首先将工人的工作时间按开始时间的升序排序,用max1记录连续至少有一人工作的最大时长,用max2记录无人工作的最大时长。start初始化为最早的开始时间,end记录满足连续条件的最晚结束时间。max每次更新为end-start的最大值。当不满足连续条件时,更新start为第一个大于end的开始时间,max2记录start-end的最大值,然后end更新为start对应工人的结束时间,直到遍历完所有工人。

C++代码

#include<iostream>
#include<algorithm>
using namespace std;
struct Worktime {
	int start;
	int end;
	Worktime(int s = NULL, int e = NULL) :start(s), end(e) {};
};
bool cmp(Worktime& a, Worktime& b)
{
	if (a.start != b.start)
		return a.start < b.start;
	return a.end < b.end;
}
int main()
{
	int N;
	cin >> N;
	Worktime* p = new Worktime[N];
	for (int i = 0; i < N; i++)
	{
		int x;
		cin >> x;
		p[i].start = x;
		int y;
		cin >> y;
		p[i].end = y;
	}
	sort(p, p + N, cmp);
	int max1 = p[0].end - p[0].start;
	int max2 = 0;
	int start = p[0].start;
	int end = p[0].end;
	for (int i = 0; i <N-1; i+=1)
	{
		if (end >= p[i+1].start)
		{
			end = p[i + 1].end > end ? p[i + 1].end : end;
			max1 = end-start> max1 ? end-start : max1;
		}
		else
		{
			start = p[i + 1].start;
			max2 =  p[i+1].start-end > max2 ? p[i+1].start - end : max2;
			end = p[i + 1].end;
		}
	}
	cout << max1 << ' ' << max2 << endl;
}

上一篇:MySQL中DELETE操作磁盘空间不会减少的原因


下一篇:【控制】遗传算法(GA,Genetic Algorithm)及 Matlab 实现