＋设为首页 ＋添加到收藏夹
有N个人排队到R个相同水龙头打水，各自装满时间T1，T2...TN为整数且互不等，如何安排使总时间最少
这道题该用什么算法？dp?
我在想是不是可以贪心贪出来
因为如果只有一个水龙头的话，那是铁定的贪心，从小到大排列就可以了
如果有r个水龙头，先把所有人按照打水时间从小到大排序，然后依次把每个人安排到等待时间最短的那个队里。
我还没想出如何证明或者证伪。
mysword(一怒拔剑) ：
用从小到大排列来分配各人所用水龙头的办法，不能保证总的等待时间最少.
例如，设有２个龙头，有５个人来打水，每人打水用的时间分别是１,2,3,4,5
按照你的规则，应让1,2先打水，然后是3,4，最后是５，如下图所示
＝＋＝ ＝＋＝
// //
|| ||
1 2
3 4
5
这时1,2,3,4,5五个人的等待时间分别为0,0,1,2,1+3,总共为7
如果改为：
＝＋＝ ＝＋＝
// //
|| ||
1 3
2 4
5
这时1,2,3,4,5五个人的等待时间分别为0,0,1,2,1+2, 总共为6, 比你的方法所用总时间少。
mysword(一怒拔剑) ：
否定了我的反例，你的办法也就能保证总时间最少了。
实际上，在打水时，每个龙头上，除了最后一个人打水时后面无人等外，其余每一个人的打水时间，都要被用作后面的人的等待时间，且排在愈前面的，在等待的人也愈多，例如，在前面的２钟方法中，
1的打水时间t1就是3,5的等待时间
2的打水时间t2就是4的等待时间
3的打水时间t3就是5的等待时间
所以，总的等待时间是 t = 2*t1 + t2 + t3,
要使t最小，只要t1为最小就可以了。
而只要等待时间最少，总的时间也就最少，因为实际在进行打水的时间的总和是不变的。
楼上的想法给了我一些启发，我来试证一下
设每个人的打水时间为t(i) 1<=i<=n，这里t(i)从小到大排好序的
假设某支队伍的组成是t(a1),t(a2)...t(ak) 其中a1<a2<..<ak，该队的队列长度为k
那么对于这支队伍所用的总时间的计算就可以变为
t=t(a1)*k+t(a2)*(k-1)+..+t(ak)*1
也就是说对某个人来说，在总时间里他所占的时间只和他的打水时间以及他所在的队列长度有关。
因此整个问题可以从另一个角度来看，即从后向前
如果把打水时间从大到小排列，即t(n),t(n-1)...t(1)，每一个人从后向前排，现在总的打水时间就决定于这些人排在哪一排
打水时间长的人肯定要排在倒数第一排，否则如果排在前面，后面有比他们时间短的人，他们的累积时间是打水时间乘以队列长度，肯定不如时间短的人排在前面划算，这一点是显然的，我就不用数学式子去罗嗦了
当倒数第一排排满之后，就排倒数第二排。这时候事实上，接下来的r个人排在哪一排都可以，因为他们都在倒数第二排，他们的累积时间是不变的。这一点和原先的谈心算法有些出入，这也就是为什么楼上举的例子中，为什么第二种排列方案和第一种排列方案所得到的总时间相同。
正因为每个人的累积时间只决定于他的打水时间和他是处在倒数第几排，因此他总是选择于排尾那个人差距最小的那一排排列，否则，如果他排在了倒数排数不是最小的那一排，那么他的累积时间对多加一次他的打水时间，而如果以后又其他人排在他应该排的那列里，总累计时间会减小其他人的打水时间那么多。而因为每个人的打水时间不同，从后向前排是按照严格地间顺序进行的，因此后面所处理的其他人的打水时间一定比他小，因此总的打水时间增加了。
用数学表示的话，就是这样：
t1 t2 .. ti
t t t t .. t
底下的t表示已经排好的，t1..ti表示正在排的那一排，ti是当前要排的那一个
按照贪心策略，ti应该排在如图所示位置，假如不排在这里，即排在前一排，如图：
ti
t1 t2 .. ti-1
t t t t .. t
那么以后如果有tj放入前一个图中ti应该放的地方，即
ti
t1 t2 .. ti-1 tj
t t t t .. t
那么总的累加时间增加了ti，因为ti多了一层，同时又至多减小了tj，因为tj可能本应该放到更高一层的，又因为严格递减，所以ti>tj，所以总时间增加了
结论：
前面所述的贪心策略没有问题，但这个问题的解答还可以拓宽，即从后向前贪心
似乎是npc的问题了
以前听过一个牛人做报告，讲的都是这类问题的近似算法
可以确定是independent task scheduling (ITS)问题，是NP完全问题
没有多项式算法，除非证明了p=np
