本文主要是介绍USACO——挤牛奶，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
洛谷 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头牛的工作时间列表，计算以下两点(均以秒为单位):
最长至少有一人在挤奶的时间段。
最长的无人挤奶的时间段。（从有人挤奶开始算起）
分析
虽然说这题是完全枚举，但是也涉及到排序。
首先将所有农夫挤奶的开始时间排序，以便枚举（同时也将农夫挤奶的结束时间一同交换）
枚举时，判断：挤奶开始时间是否与之前的农夫挤奶结束时间交错，以及要将最大挤奶时间开始及结束记录好
#include <iostream>
using namespace std;
int a[5001][2],m1,m2,i,n,t1,t2;
void qs(int l,int h)
{int i=l,j=h,mid=a[(l+h)/2][1],t;do{while (a[i][1]<mid) i++;while (a[j][1]>mid) j--;if (i<=j){t=a[i][1];a[i][1]=a[j][1];a[j][1]=t;t=a[i][2];a[i][2]=a[j][2];a[j][2]=t;i++;j--;}}while (i<=j);if (i<h) qs(i,h);if (j>l) qs(l,j);return;
}
int main()
{cin>>n;for (i=1;i<=n;i++)cin>>a[i][1]>>a[i][2];qs(1,n);t1=a[1][1];t2=a[1][2];m1=t2-t1;for (i=2;i<=n;i++){if (t2<a[i][1]){if (a[i][1]-t2>m2) m2=a[i][1]-t2;if (a[i][2]-a[i][1]>=m1) m1=a[i][2]-a[i][1];t1=a[i][1];t2=a[i][2];}if (t2>=a[i][1]&t2<=a[i][2]) {if (a[i][2]-t1>=m1) m1=a[i][2]-t1;t2=a[i][2];}}cout<<m1<<" "<<m2;return(0);
}这篇关于USACO——挤牛奶的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
