这一次刷题目纯粹是为了Noip的复赛，因为不知道Noip复赛是否能够使用qsort函数，所以就只能自己写了，在函数实现方面出现了不少错误，原计划时提交一次就AC的，但是却提交了4次，下面先贴出思路，再贴出具体的错误。
现将程序按照开始的时间进行一次排序，然后对排序后的数组进行一次迭代(far[i])，用一个now结构记录当前最长连续的开始时间和结束时间，如果far[i]的结束时间小于等于now的开始时间，那么now的开始时间不变，因为是排过续得了，但是结束时间就可能要更新了，如果far[i]的结束时间大于now的结束时间的话；如果far[i]的开始时间大于now的结束时间的话，那就是说这期间有一个没有人挤牛奶的时间，那就先判断now的开始时间到结束时间是否是最长的有人挤奶的时间，然后判断far[i]的开始时间和now的结束时间的差是否是最长无人挤奶的时间。
错误如下：
2、好久没写快排了，这一次写了快排的函数，但是竟然忘记递归调用自己了！有些吓人的错误。。
这样的话，如果a = 3, b = 2, c = 1，那么排序之后的结果是2, 1, 3而不是期望的1, 2, 3，原因很简单，因为最小的被放在了中间，而两边的却不是最小的，所以正确的方法应该是先把最小/最大的位置放对，然后再把剩下的一对比较放好就是：
LANG: C
ID: logoo2
PROG: milk2
/
#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
#define min(a, b) ((a)<(b)?(a):(b))
#define swap(a, b) do{\
struct far tmp;\
tmp = a;\
a = b;\
b = tmp;\
}while(0)
struct far{
int start, end;
}far[5000];
int com(struct far a, struct far b)
{
return a->start – b->start;
}
void insert_sort(int s, int t)
{
int i, j;
struct far key;
for(i = s + 1; i <= t; i++){
key = far[i];
/
mistack 3:
下面的j >= s 写成了 j >= 0
/
for(j = i – 1; com(&key, &far[j]) < 0 && j >= s; j–){
far[j + 1] = far[j];
}
far[j + 1] = key;
}
}
void choose(int s, int t)
{
int mid = (s + t) / 2;
/
mistack 5:
下面比较的顺序原来是:
if(com(&far[mid], &far[s]) < 0){
swap(far[mid], far[s]);
}
if(com(&far[mid], &far[t]) > 0){
swap(far[mid], far[t]);
}
if(com(&far[s], &far[t]) > 0){
swap(far[s], far[t]);
}
但是碰到, far[s] > far[mid] > far[t] 的情况就会出问题..
/
if(com(&far[mid], &far[s]) < 0){
swap(far[mid], far[s]);
}
if(com(&far[s], &far[t]) > 0){
swap(far[s], far[t]);
}
if(com(&far[mid], &far[t]) > 0){
/
mistack 4:
误把下面的far[t]写成了far[s]
/
swap(far[mid], far[t]);
}
swap(far[t – 1], far[mid]);
}
void sort(int s, int t)
{
int i, j;
if(t – s < 9){
insert_sort(s, t);
return ;
}
choose(s, t);
i = s, j = t – 1;
while(i < j){
while(com(&far[++i], &far[t – 1]) < 0){
continue;
}
while(com(&far[–j], &far[t – 1]) > 0){
continue;
}
if(i < j){
swap(far[i], far[j]);
}
}
swap(far[t – 1], far[i]);
/
mistack 2:
对快排的代码并不是特别的熟练，打完了上面的代码后忘记继续进行递归了。。
/
sort(s, i – 1);
sort(i + 1, t);
}
int main(void)
{
int n;
int i;
struct far now;
int ans1 = 0, ans2 = 0;
freopen("milk2.in", "r", stdin);
freopen("milk2.out", "w", stdout);
scanf("%d\n", &n);
for(i = 0; i < n; i++){
scanf("%d%d", &far[i].start, &far[i].end);
}
// qsort(far, n, sizeof(struct far), com);
sort(0, n – 1);
now = far[0];
for(i = 1; i < n; i++){
if(far[i].start <= now.end){
now.end = max(now.end, far[i].end);
}else{
if(now.end – now.start > ans1){
ans1 = now.end – now.start;
}
if(far[i].start – now.end > ans2){
ans2 = far[i].start – now.end;
}
now = far[i];
}
}
/
mistack 1:
在退出循环时应该把最后剩下的数据进行判断.
/
if(now.end – now.start > ans1){
ans1 = now.end – now.start;
}
printf("%d %d\n", ans1, ans2);
return 0;
}