一道关于贪心算法的题，始终无法AC！
题目网址：http://wikioi.com/problem/2079/这次的题目依旧是贪心类别的，但是比较郁闷的是，没能最终写出AC的算法来，实在检查不出问题出在哪里，放一段时间再看吧。各位在看我日志的大牛，如果您有一丢丢小空余时间，然后，又觉得没有什么具体的事情好做，想要轻松一下，放松一下大脑的话，麻烦帮忙看一下是哪里的问题吧。在OJ验证的话，只能通过一半的数据。检查过排序算法，检查了最后数据的处理，应该没有越界的情况，我也实在想不出有什么诡异的数据来测试了。代码里面有比较详细的注释，有问题的话随时口以交流。谢谢哈http://static.blog.csdn.net/xheditor/xheditor_emot/default/smile.gif/*1、统计间隔信息，排序；
2、按照所给板子块数，切开；
要使木板总长度最少，就要使未盖木板的长度最大。
我们先用一块木板盖住牛棚，然后，每次从盖住的范围内选一个最大的空隙，以空隙为界将木板分成两块，重复直到分成m块或没有空隙。
*/
#include <stdio.h>
//快速排序算法
void quick(int *input,int l,int r)
{
if( l < r )
{
int i = l,j = r, x = input;
while(i<j)
{
while(i<j && input <= x)// right to left to find the bigger than x
j--;
if(i < j)
input = input;
while(i<j && input >= x)// left to right to find the minner than x
i++;
if( i< j)
input= input;
}
input = x;
quick(input,l ,i-1);
quick(input, i+1 ,r);
}
}
int main()
{
int M,S,C;
int max_milk;
int dis;
scanf("%d %d %d",&M,&S,&C);
int i,j;
int len_dis;
for(i=0 ; i< C ; i++)
{
scanf("%d",&max_milk);
}
//获取间隔值
for(i=0,j=0 ; i< C-1 ; i++)
{
if( max_milk- max_milk >1)
{
dis = max_milk - max_milk-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;
}
//去掉头，去掉尾，留下最后盖了板子的
printf("%d", S - (max_milk-1) - (S-max_milk) - count);
return 0;
}
最终解决了。我在设计的时候，默认把输入数据当做是有序的了。
应当在开始的时候，在拍一遍序。 谢谢楼主分享！ 路过看看 = = 谢谢楼主分享！
页:
[1]