题目网址: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;
- }
复制代码
|