| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 703 人关注过本帖
标题:pku acm 1042 “gone fishing” 出现“wrong answer”
取消只看楼主 加入收藏
lyhlyhlyhboa
Rank: 2
来 自:西安电子科技大学
等 级:论坛游民
帖 子:60
专家分:23
注 册:2011-1-1
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:2 
pku acm 1042 “gone fishing” 出现“wrong answer”
这是原题地址http://
    题目大概意思是这样的:在一条水平路边,有n(2<=n<=25)个湖,从左到右序号为1,2,3…n。佳佳有H个小时的空余时间,他希望用这些时间钓鱼。他从1号湖出发向右走,有选择地在一些湖边停留一定的时间来钓鱼,最后在某个湖边结束钓鱼。他已测出,从第i个湖到第i+1个湖要走Ti分钟的路。他还测出,在第i个湖的第一个5分钟可钓鱼Fi条,以后每钓鱼5分钟,可钓鱼量减少Di。假定没有其他人钓鱼,也不受其他因素影响,编程求出佳佳钓鱼最多的方案。

    用的是枚举加贪心的算法,提交后显示“wrong answer”,也就是结果错误,但是已经给出的输入输出范例在这个程序中都是切合的,所以我不知道是在什么样的输入情况下会出现结果错误,麻烦各位大虾帮我看下,是什么情况下会结果错误,或是指出我有可能忽略了的某个重要问题。。多谢!
    下面是C程序代码:
程序代码:
#include <stdio.h>
#include <stdlib.h> 

void f_DataCopy(int *, int *, int);
int f_BestProject(int *, int *, int *, int, int);
void f_print(int *, int);
int f_max(int *, int);
int main()
{
    int i, j, tmp;
    
    int n, h, min_5, num = 0;
    int * _fi;                        //暂时保存fi,便于还原fi
    int * fi;                         //第i个湖泊每5分钟能钓到的鱼 
    int * di;                         //第i个湖泊每间隔5分钟钓到鱼的减少量 
    int * ti;                         //从第i个到第i+1个湖泊所需时间(5分钟为单位)
    int * Tmp;                        //用于暂时存放时间分配情况 
    int * Ti;                         //在第i个湖泊停留的时间 
    
    scanf("%d", &n);
    while (n)
    {
          _fi = (int *)malloc(n * sizeof(int));
          fi = (int *)malloc(n * sizeof(int));
          di = (int *)malloc(n * sizeof(int));
          ti = (int *)malloc((n-1) * sizeof(int));
          Ti = (int *)malloc(n * sizeof(int));
          Tmp = (int *)malloc(n * sizeof(int));
          
          scanf("%d", &h);
          min_5 = h * 60 / 5;
          
          for (i = 0; i < n; i++)
              scanf("%d", &fi[i]);
          for (i = 0; i < n; i++)
              scanf("%d", &di[i]);
          for (i = 0; i < n-1; i++)
              scanf("%d", &ti[i]);
          for (i = 0; i < n; i++)
              Ti[i] = 0;
          for (i = 0; i < n; i++)
              Tmp[i] = 0;
              
          f_DataCopy(_fi, fi, n);
              
          //枚举最后一个岛的可能情况 
          for (i = 0; i < n; i++)
          {
              if (i != 0)
                 for (j = 0; j < i; j++) min_5 -= ti[j];
              
              if ( (tmp = f_BestProject(fi, di, Tmp, i+1, min_5)) > num )
              {
                   num = tmp;
                   f_DataCopy(Ti, Tmp, n);
              }
              
              //还原fi,min_5及数组Tmp[]为初始值 
              f_DataCopy(fi, _fi, n);
              min_5 = h * 60 / 5;
              for (j = 0; j < n; j++)
                  Tmp[j] = 0;
          }
          
          f_print(Ti, n);
          printf("Number of fish expected: %d\n\n", num); 
          
          free(_fi);
          free(fi);
          free(di);
          free(ti);
          free(Ti);
          free(Tmp);
          
          num = 0;
          
          scanf("%d", &n);
     }
     
     return 0;
}

//在确定最后一个岛的情况下取得最优解 
int
f_BestProject(int * fi, int * di, int * Tmp, int n1, int min_5)
{
                  int i, j;
                  int num = 0;
                  
                  for (i = min_5; i > 0; i--)
                  {
                      j = f_max(fi, n1);
                      Tmp[j]++;
                      if (fi[j] > 0)
                         num += fi[j];
                      fi[j] -= di[j];
                  }
                  
                  return num;
}

//按格式输出 
void
f_print(int * Ti, int n)
{
            int i;
            for (i = 0; i < n; i++)
            {
                if (i == n-1)
                   printf("%d\n", Ti[i] * 5);
                else
                   printf("%d, ", Ti[i] * 5);
            }
}

//将等长的string2复制到string1 
void 
f_DataCopy(int * string1, int * string2, int n)
{
               int i;
               for (i = 0; i < n; i++)
                   string1[i] = string2[i];
}

//取得数组中前n个数中最大数的下标 
int
f_max(int * fi, int n1)
{
          int i, j = 0;
          int tmp = fi[0];
          
          for (i = 1; i < n1; i++)
          {
              if (fi[i] > tmp && fi[i] > 0)
              {
                        tmp = fi[i];
                        j = i;
              }
          }
          
          return j;
}
          


[ 本帖最后由 lyhlyhlyhboa 于 2013-10-10 19:13 编辑 ]
搜索更多相关主题的帖子: wrong 佳佳 影响 
2013-10-10 19:09
lyhlyhlyhboa
Rank: 2
来 自:西安电子科技大学
等 级:论坛游民
帖 子:60
专家分:23
注 册:2011-1-1
收藏
得分:0 
没人啊..求援助啊

不懈
2013-10-10 20:58
lyhlyhlyhboa
Rank: 2
来 自:西安电子科技大学
等 级:论坛游民
帖 子:60
专家分:23
注 册:2011-1-1
收藏
得分:0 
回复 3楼 azzbcc
感激不尽!!!
终于...开始这句话有点理解错了,以为在枚举的时候已经实现了这句话,看来以后英文题还是得一词一词仔细看啊!

不懈
2013-10-10 22:41
快速回复:pku acm 1042 “gone fishing” 出现“wrong answer”
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.044599 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved