milk2解题报告 —— icedream61 博客园（转载请注明出处）
------------------------------------------------------------------------------------------------------------------------------------------------
【题目】
N个农民，每个农民从L[i]到R[i]时间给奶牛挤奶。问最长的一直有人挤奶的时间，和最长的没有人挤奶的时间。
【数据范围】
1<=N<=5000
0<=L[i],R[i]<=1,000,000
【输入样例】
3
300 1000
700 1200
1500 2100
【输出样例】
900 300
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
先对N个农民按照L[i]排序，然后顺序扫。
我用Sum[0]记录最长一直没人挤奶的时间，用Sum[1]记录最长一直有人挤奶的时间。
用Lt记录当前所考虑的开始时间，Rt记录当前所考虑的结束时间。
“a←b”表示用b更新a，即 if(b>a) a=b;
开始 Lt=L[1]; Rt=R[1];
如果 R[i]<L[i+1]，说明i和i+1时间分开了，那么 Sum[0]←L[i+1]-Rt; Sum[1]←Rt-Lt;
否则，说明i+1可以和i的挤奶时间连上，那么 Rt←R[i+1];
算法描述完毕，注意别写错就好。
------------------------------------------------------------------------------------------------------------------------------------------------
【总结】
一遍AC。
复习了下快排～
还有由于直接上手写的代码，代码不漂亮：
1.bool变量p没用上
2.L和R如果定义成Time类型，和T[]保持一致就更好看了
------------------------------------------------------------------------------------------------------------------------------------------------
【代码】
/*
ID: icedrea1
PROB: milk2
LANG: C++
*/ #include <iostream>
#include <fstream>
using namespace std; int N;
struct Time { int b,g; } T[+]; void qsort(Time T[],int l,int r)
{
if(l>=r) return; int i=l,j=r,x=T[(l+r)>>].b;
while(true)
{
while(T[i].b<x) ++i;
while(T[j].b>x) --j;
if(i>j) break;
Time t=T[i]; T[i]=T[j]; T[j]=t;
++i; --j;
}
qsort(T,l,j); qsort(T,i,r);
} void change(int &a,int b)
{
if(b>a) a=b;
} int main()
{
ifstream in("milk2.in");
ofstream out("milk2.out"); in>>N;
for(int i=;i<=N;++i) in>>T[i].b>>T[i].g; qsort(T,,N); bool p; // Ture挤奶，F空闲
int L,R; // 当前时间段
int Sum[]={,}; // 最大值——0空闲时间，1挤奶时间 L=T[].b; R=T[].g;
for(int i=;i<=N;++i)
{
if(R<T[i+].b) // 挤奶时间完结
{
change(Sum[],T[i+].b-R);
change(Sum[],R-L);
L=T[i+].b; R=T[i+].g;
}
else // 更新挤奶时间
{
change(R,T[i+].g);
}
}
change(Sum[],R-L); out<<Sum[]<<" "<<Sum[]<<endl; in.close();
out.close();
return ;
}