跳至正文

USACO 1.3.2 Barn Repair

  • OI路程

  这一题想了好久才想起来以前是怎么做的,直接使用的贪心,首先假设只有一块木板,自然而然是从最小的到最大的全部盖上,此时假设值为ans,那么如果是两块木板,那两块木板之间隔的距离必定是整个牛棚中距离最远的两个牛之间的距离,也就是说答案等于:只有一块木板的长度减去一个最长间隔:ans-max(dis),那三块木板的话很自然就是只有一块木板的长度减去最长的前两个间隔的值,以此类推,代码就很简单了。
  但是又由于需要快排的实现,我嫌它麻烦了,就直接使用数组进行排序(这个排序方法准确叫什么名字我也忘了,不记得是基数还是桶还是哈希排序了。),因为数据量并不是特别的大,所以使用这种排序方法也会比快排要好很多(至少自我感觉是这样,我的应该是O(n)而快排最快O(n logn))!
  这也是少量提交了两次的题目:

  1、在程序中如果有n块木板的话,相当于只有一块木板,其中有n-1个洞;也就是说一块肉要3块只要切2刀即可。j = 1; j < m
  2、比如已有a, b 两点(b > a),代表两个位置,那么b – a – 1代表的是把两点除去,剩下的个数,而b – a + 1代表包括亮点总共的长度,在求只要一块木板长度时应该是b-a+1,我写的是b-a-1。
  3、程序的设计有误,求下一点应该是从+1开始而不是从当前点开始,这一个我不好形象点地说出来,只能说j要从1开始,之后的内容要修改成dis[j – 1]++。
  下面这个是第二次提交之后发现的问题。
  4、下面的代码忽略了一个重要的问题:
for(i = s – 1; i >= 0 && j < m; i–){
if(dis[i] > 0){
ans -= i;
j++;
dis[i]–;
}
}
  当dis[i] > 1时只计算一次,剩下的次数就不算了。。
  修改之后(在dis[i]–;后面插入i++;一行)就能够应付了。
  还有一个要注意的,就是在循环体退出之后还要一个dis[j – 1]–;因为前面会把最后一个牛和结尾的墙壁之间的距离当作需要考虑的距离来算,要将它除去。
/
LANG: C
ID: yylogoo2
PROG: barn1
/
#include <stdio.h>
int cow[200];
int dis[200];

int main(void)
{
        int t;
        int i, j;
        int m, s, c;
        int fi = 200, la = –1;
        unsigned ans;
        freopen("barn1.in""r"stdin);
        freopen("barn1.out""w"stdout);
        scanf("%d%d%d", &m, &s, &c);
        for(i = 0; i < c; i++){
                scanf("%d", &t);
                cow[t – 1]++;
                if(t – 1 < fi){
                        fi = t – 1;
                }
                if(t – 1 > la){
                        la = t – 1;
                }
        }
        i = fi;
        while(i < s){
                /
                Mistack 3:
                  下面应该从1开始,而不是0,不然会进入死循环,
                但是下面改成一之后dis[j]++就要改成dis[j – 1]++。
                
/
                for(j = 1; (cow[i + j] == 0) && (i + j < s); j++){
                }
                dis[j – 1]++;
                /
                Pay attention:
                  下面-1的原因是再进行计算一次
                
/
                i += j;
        }
        /
          下面的代码是把最后一个位置和结尾之间的空隙删除了
        其实它可以放在上面的循环体内, 但是这样的话每次循环都
        要判断一次, 很慢!!
        
/
        dis[j – 1]–;
        /
        Mistack 2:
          下面应该是要+1而不是-1
        +1代表包括两点中间的距离,
        -1代表出去两点中间的距离。
        
/
        ans = la – fi + 1;
        /
        Mistack 1:
          下面应该是从1开始而不是0, 因为把一块肉切成3分的话,只要2刀 
        
/
        j = 1;
        /
        Mistack 4:
          下面的代码忽略了一个重要的问题:
        for(i = s – 1; i >= 0 && j < m; i–){
                if(dis[i] > 0){
                        ans -= i;
                        j++;
                        dis[i]–;
                }
        }
          当dis[i] > 1时只计算一次,剩下的次数就不算了。。
          修改之后(在dis[i]–;后面插入i++;一行)就能够应付了。 
        
/
        for(i = s – 1; i >= 0 && j < m; i–){
                if(dis[i] > 0){
                        ans -= i;
                        j++;
                        dis[i]–;
                        i++;
                }
        }
        printf("%u\n", ans);
        return 0;
}

发表回复

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