Question

C语言！ 求教。

这样···有一个送水工人，住在L楼；有N个在不同楼的用户定了水；每天早上6点，公司把水放在送水工的门口。。。。6点整送水工开始送水。一分钟跑一层楼，(忽略其他时间);
怎样送水可以使客户不满意度之和最小？ （输出最小的不满意度之和就好）
每个客户的不满意度是指客户收到牛奶的时刻与6点的差（分钟）

比如输入 1 9 11 19（4个订奶的） 10（送奶工所在楼层）
输出 44（这是最小的客户不满意度之和）

我的想法是把所有的送法对应的不满意度之和全部求出来，输出最小的那个。
不知道怎么实现?_?
怎么破？

Answer 1

算法设计学过吗，全排列算法。
你想遍历所有送法，只要产生全排列即可。
#include <stdio.h>
#include <math.h>
int A[] = {10,1,9,11,19}, N = 4, //N个用户，数组A[1...N]存储N个用户的楼层，A[0]存储送水工所在楼层
MIN = 10000;
//交换元素
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
//产生全排列
void func(int n)
{
int i, t = 0;
if(n==N) //递归叶子节点
{
for(i=0; i<N; i++) //计算不满意度之和
t += abs(A[i]-A[i+1])*(N-i);
if(MIN > t)MIN = t; //更新MIN
return;
}
//递归过程
for(i=n; i<=N; i++)
{
swap(A+n, A+i);
func(n+1);
swap(A+n, A+i);
}
}
int main()
{
func(1); //函数调用
printf("%d", MIN);
}

追问

是要可以输入 N L；
然后根据N 输入楼层数。。。。。
N为4的时候是那样。。。
N为5的时候就要输入 5个数据。

追答

写这个程序只是告诉你怎么求解这个问题。这是核心代码。
这个例子看懂了再自己修改成输入

Answer 2

这个题目和磁盘调度算法类似啊，可以去操作系统里面查询下，磁盘调度，最小距离调度算法，电梯算法。。。。

Answer 3

Answer 4