一道关于贪心算法的题，始终无法AC！

压寨宝宝

题目网址：http://wikioi.com/problem/2079/

这次的题目依旧是贪心类别的，但是比较郁闷的是，没能最终写出AC的算法来，实在检查不出问题出在哪里，放一段时间再看吧。

各位在看我日志的大牛，如果您有一丢丢小空余时间，然后，又觉得没有什么具体的事情好做，想要轻松一下，放松一下大脑的话，麻烦帮忙看一下是哪里的问题吧。

在OJ验证的话，只能通过一半的数据。

检查过排序算法，检查了最后数据的处理，应该没有越界的情况，我也实在想不出有什么诡异的数据来测试了。

代码里面有比较详细的注释，有问题的话随时口以交流。谢谢哈

                               
登录/注册后可看大图

/*
1、统计间隔信息，排序；
2、按照所给板子块数，切开； 

要使木板总长度最少，就要使未盖木板的长度最大。
我们先用一块木板盖住牛棚，然后，每次从盖住的范围内选一个最大的空隙，以空隙为界将木板分成两块，重复直到分成m块或没有空隙。
*/
#include <stdio.h>
//快速排序算法 
void quick(int *input,int l,int r)
{
        if( l < r )
        {
                int i = l,j = r, x = input[l];
                while(i<j)
                {
                        while(i<j && input[j] <= x)// right to left to find the bigger than x
                                j--;
                        if(i < j)
                                input[i++] = input[j];
                        while(i<j && input[i] >= x)// left to right to find the minner than x
                                i++;
                        if( i< j)
                                input[j--]= input[i];
                }
                input[i] = x;
                quick(input,l ,i-1);
                quick(input, i+1 ,r);
        }
}

int main()
{
        int M,S,C;
        int max_milk[210];
        int dis[210];
        scanf("%d %d %d",&M,&S,&C);
        int i,j;
        int len_dis;
        for(i=0 ; i< C ; i++)
        {
                scanf("%d",&max_milk[i]);
        }
        //获取间隔值 
        for(i=0,j=0 ; i< C-1 ; i++)
        {
                if( max_milk[i+1]- max_milk[i] >1)
                {
                        dis[j++] = max_milk[i+1] - max_milk[i]-1;
                }
        }
        //排序
        len_dis = j;
        quick(dis,0,len_dis-1);

        int count=0;
        //按照木板数切割 
        //重复直到分成m块 i < M-1 或者没有空隙   i < len_dis
        for(i=0 ; i < M-1 && i < len_dis; i++)
        {
                count += dis[i];
        }
        //去掉头，去掉尾，留下最后盖了板子的 
        printf("%d", S - (max_milk[0]-1) - (S-max_milk[C-1]) - count);
        return 0;
}

压寨宝宝

最终解决了。我在设计的时候，默认把输入数据当做是有序的了。
应当在开始的时候，在拍一遍序。

冷暖自知

谢谢楼主分享！

未闻丶花名

路过看看 = =

千亩计者

谢谢楼主分享！