切换到宽版
发帖 回复
返回列表
  • 4673阅读
  • 1回复

发个贪心题目 [复制链接]

 上一主题 下一主题
离线ly365
OIFans入门选手
 
只看楼主 倒序阅读 0 发表于: 2006-10-25
]有一栋楼房发火灾了,有N个人水龙头可以接水,有R个人拿桶去接水救火,为了救火,节约时间,
用什么方法打水可以在最短的时间内,让每个人的桶子都装满水?
输入
N R
4 6
6 9 2 1 5 3

输出
29
回复
举报
分享到 淘江湖 新浪 QQ微博 QQ空间 开心 人人 豆瓣 网易微博 百度 鲜果 白社会 飞信
离线ly365
OIFans入门选手
只看该作者 1 发表于: 2006-10-27
没人帮助我解决.我还是自己来写了一个..大家看下能优化么?


  var b,n,m,i,j,r,temp,o,t1,t2:integer;

    f1,f2:text;
    a:array[0..1000] of integer;

begin
  fillchar(a,sizeof(a),0);
  a[0]:=0;
assign(f1,'e:\ly\water\water.in');
reset(f1);
readln(f1,n,r);
for i:=1 to n do read(f1,a);
for i:= 1 to n-1 do         {排序}
  for j:=I+1 to n do if a >a[j] then
  begin
  temp:=a;
  a:=a[j];
  a[j]:=temp;
  end;

if r>=n then a[0]:=a[0]+a   {如果龙头大于桶}
else                           {桶大于龙头的情况}
  begin                      
t1:=n div r;
t2:=n mod r;
  for i:=1 to n do a[0]:=a[0]+a;     {a[0]记录时间,因为龙头出水的时间是一定的,先把出水的总时间求出来.}
  for i:=1 to t1 do
  begin
    for j:=1 to r do

    a[0]:=a[0]+a[j+o]*(t1-i);   {接下来可以把水桶看成一个R*t1的矩证, 第一排的R个水桶打水时间*t1表示下面等待时间,第2列*(t1-1)}

    o:=o+r; {累计加R}
  end;

  n:=0;

  if t2 >0 then begin {出来非完全矩证,再累加到A[0]}

  while t2 > n do
  begin
        n:=n+1;
    for i:=1 to t1*r do
    if i mod r = n then a[0]:=a[0]+a;


  end;

  end;

  end;

  assign(f2,'e:\ly\water\water.out');
  rewrite(f2);
  write(f2,a[0]);
  close(f1);
  close(f2);
end.




测试数据
water.in
6 4
1 6 5 2 9 3


water.in
6 2
1 6 5 2 9 3


第一组输出 29
第二组输出 40
[ 此贴被ly365在2006-10-29 19:40重新编辑 ]
回复
举报
发帖 回复
返回列表
快速回复
限100 字节
 
上一个 下一个