排队打水问题 [复制链接]

有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…..，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少？

program pdgs;
var a:array[1..125,1..125]of integer;
  b:array[1..125]of integer;
  x,y,z,n,r,o,j,c,k:integer;
begin
readln(n,r);
for x:=1 to n do read(b[x]);
for x:=1 to n-1 do
  for y:=x+1 to n do
    if b[x]>b[y] then begin
    z:=b[x];
    b[x]:=b[y];
    b[y]:=z;
    end;
for x:=1 to n div r do
  for y:=1 to r do
    a[x,y]:=(x-1)*r+y;
if n mod r>0 then
  for x:=1 to n mod r do
    a[n+1,x]:=n div r*r+x;
z:=0;
for x:=1 to n do begin
  z:=z+b[x];
  y:=x mod r;
  if x>r then begin
    o:=0;
    k:=x div r;
    if y=0 then k:=k-1;
    for j:=1 to k do begin
    if y=0 then y:=y+r;
    c:=a[j,y];
    o:=o+b[c];
            end;
    z:=z+o;
    end;
  end;
writeln(z);
end.

贪心法题目

能不能打水打倒一半换水龙头

贪心的基本算法。。。。。。

输入样例:
4 2
2 6 4 5
运行结果输出:23
可是这里总共才四个人去打水,有两个小龙头,就算是只有一个水龙头,
也只要2+6+4+5=17的时间.怎么会最少还要花费23的时间呢?

贪心吗。。？我怎么觉得是DP。。？

题意不清，到底是所有人总时间最短还是所有水龙头中最长时间最短？
如果是所有人时间最短的话用贪心很好做，但如果是求所有水龙头中最长时间最短的话，貌似用DP也很难啊。

同意楼上。
如果是求所有水龙头中最长时间最短的话，ms只能用搜索了。