鱼C论坛

 找回密码
 立即注册
查看: 3493|回复: 4

一道关于贪心算法的题,始终无法AC!

[复制链接]
发表于 2014-2-2 21:05:16 | 显示全部楼层 |阅读模式
10鱼币

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

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

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

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

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

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


                               
登录/注册后可看大图

  1. /*
  2. 1、统计间隔信息,排序;
  3. 2、按照所给板子块数,切开;

  4. 要使木板总长度最少,就要使未盖木板的长度最大。
  5. 我们先用一块木板盖住牛棚,然后,每次从盖住的范围内选一个最大的空隙,以空隙为界将木板分成两块,重复直到分成m块或没有空隙。
  6. */
  7. #include <stdio.h>
  8. //快速排序算法
  9. void quick(int *input,int l,int r)
  10. {
  11.         if( l < r )
  12.         {
  13.                 int i = l,j = r, x = input[l];
  14.                 while(i<j)
  15.                 {
  16.                         while(i<j && input[j] <= x)// right to left to find the bigger than x
  17.                                 j--;
  18.                         if(i < j)
  19.                                 input[i++] = input[j];
  20.                         while(i<j && input[i] >= x)// left to right to find the minner than x
  21.                                 i++;
  22.                         if( i< j)
  23.                                 input[j--]= input[i];
  24.                 }
  25.                 input[i] = x;
  26.                 quick(input,l ,i-1);
  27.                 quick(input, i+1 ,r);
  28.         }
  29. }

  30. int main()
  31. {
  32.         int M,S,C;
  33.         int max_milk[210];
  34.         int dis[210];
  35.         scanf("%d %d %d",&M,&S,&C);
  36.         int i,j;
  37.         int len_dis;
  38.         for(i=0 ; i< C ; i++)
  39.         {
  40.                 scanf("%d",&max_milk[i]);
  41.         }
  42.         //获取间隔值
  43.         for(i=0,j=0 ; i< C-1 ; i++)
  44.         {
  45.                 if( max_milk[i+1]- max_milk[i] >1)
  46.                 {
  47.                         dis[j++] = max_milk[i+1] - max_milk[i]-1;
  48.                 }
  49.         }
  50.         //排序
  51.         len_dis = j;
  52.         quick(dis,0,len_dis-1);

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


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2014-2-4 20:30:49 | 显示全部楼层
最终解决了。我在设计的时候,默认把输入数据当做是有序的了。
应当在开始的时候,在拍一遍序。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2014-2-5 23:36:46 | 显示全部楼层
谢谢楼主分享!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2014-2-8 20:47:09 | 显示全部楼层
路过看看 = =
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-8-16 23:25:09 | 显示全部楼层
谢谢楼主分享!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 20:02

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表