跳至正文

USACO 1.2.1 Milking Cows

  • OI路程

  这一次刷题目纯粹是为了Noip的复赛,因为不知道Noip复赛是否能够使用qsort函数,所以就只能自己写了,在函数实现方面出现了不少错误,原计划时提交一次就AC的,但是却提交了4次,下面先贴出思路,再贴出具体的错误。
  现将程序按照开始的时间进行一次排序,然后对排序后的数组进行一次迭代(far[i]),用一个now结构记录当前最长连续的开始时间和结束时间,如果far[i]的结束时间小于等于now的开始时间,那么now的开始时间不变,因为是排过续得了,但是结束时间就可能要更新了,如果far[i]的结束时间大于now的结束时间的话;如果far[i]的开始时间大于now的结束时间的话,那就是说这期间有一个没有人挤牛奶的时间,那就先判断now的开始时间到结束时间是否是最长的有人挤奶的时间,然后判断far[i]的开始时间和now的结束时间的差是否是最长无人挤奶的时间。
  错误如下:

  1、唯一一个不是快排实现的问题,在退出循环之后应该是还要判断一下now的时间是否是最长有人挤奶的时间。
  2、好久没写快排了,这一次写了快排的函数,但是竟然忘记递归调用自己了!有些吓人的错误。。
  3、我的快排的话,在元素个数在较少时直接调用插入排序,但是插入排序中间的第二层循环的条件写错了,把j>=s 写成了 j >=0。
  4,5、都是出现在选择枢纽元的函数里面,有一个确实错的很惨,可以这么表示:
             if(a > b){
               max = b;
             }
  明显应该是max = a,这种错误,确实很惨,还有另外一个错误可以这么表示,有三个数a, b, c要求按顺序排序这三个数,我的错误的排序方法是:

if(com(&a, &b) < 0){
swap(a, b);
}
if(com(&b, &c) > 0){
swap(b, c);
}
if(com(&a, &c) > 0){
swap(a, c);
}
  这样的话,如果a = 3, b = 2, c = 1,那么排序之后的结果是2, 1, 3而不是期望的1, 2, 3,原因很简单,因为最小的被放在了中间,而两边的却不是最小的,所以正确的方法应该是先把最小/最大的位置放对,然后再把剩下的一对比较放好就是:
if(com(&a, &b) < 0){
swap(a, b);
}
if(com(&a, &c) > 0){
swap(a, c);
}
if(com(&b, &c) > 0){
swap(b, c);
}
  Ok了,把错误终结了,我就能够继续前进了,代码如下:
/
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;
}

发表回复

您的电子邮箱地址不会被公开。