您正在看的Windows XP是:挑战2004年高校bbs程序大赛算法设计第一名－－－－打水问题。

挑战2004年高校bbs程序大赛算法设计第一名－－－－打水问题

我的程序绝对比他的优。。。。

/* 打水问题的最优化算法 */

/* 算法设计：最小打水时间的设计；一共有N个人打水，R个水源头，所以他们的打水时间的最小用时，不会低于他们的每个人所用时间的最大值---max(T1,T2,------Tn)。*/

/*第一种情况，*/

/*当N<=R时，N个人每个人同时所用R个水龙头，他们所用最小的打水时间为max(T1,T2,------Tn)。*/

/* 第二种情况，*/

/*当N>R时，基本思想为，用时最大的人先打水原则。所以先把打水的人安从大到小的顺序，*/

/* 让用时多的人先用水龙头，把N个人中，用时在前R的人排成一排，*/

/*成为一组所用水龙头的人，然后在剩余的人中，把用时最大的人排在前一排用时最小的人的后面。然后计算每个水龙头的总共用时数，*/

/* 然后把剩余的人中用时最大的人排在水龙头*/

/* 总共用时数最小的那列，以此排列，直到把人排完。*/

/* 算法的数学模型。 */

/* 已知：一共有N个人打水，R个水源头，N个人的打水时间为：T1,T2,------Tn。*/

/* 把N个人的用时排序后，设为：S1,S2,-------Sn,S1＝max(T1,T2,------Tn)表示用时最大的人，Si表示第i个最大用时者。*/

/* 第一排的人为S1,S2,------SR,*/

/* 剩余人数为N－R，第一排用时的最大数为S1,最小者为SR，在SR后面排SR+1，( SR+1为剩余人中用时最大者 )。然后计算各个水龙头的总共用时数，*/

/* 第一水龙头的总共用时量为S1，第i个水龙头的总共用时量为Si，最后一个水龙头的总共用时量为SR+SR+1)。找出最小用时的水龙头，把SR+2排在该列，*/

/* 如此循环，假如，在某次排列后的情况为：第一列的总共用时量为A1，第I列的总共用时量为Ai，第R列的总共用时量为AR，*/

/*水龙头总共用时量最小者为Aj,及Aj=min(A1,A2,----,AR)。*/

/* 现在，剩余的人中用时最大者的用时量为B，把B加到Aj那列，此时该列的总共用时量为：B+Aj。因为 */

/* Aj<=Ai,( i!=j ， 1<=i,j<=R )。 所以 Aj+B<=Ai+B 。 */

/* 编程 */

#include <stdio.h>

#include <malloc.h>

#define list_node_size sizeof(struct list_task)

#define tree_node_size sizeof(struct tree_node)

struct list_task

{

int tasks;

struct list_task * next,* up;

};

struct tree_node

{

int tasks;

struct tree_node * right_child,* left_child;

};

struct list_task * input_task(int n)

{

int i;

struct list_task *head,*p1,*p2;

p1=(struct list_task *)malloc(list_node_size);

printf("please input size of task1:");

scanf("%d",&p1->tasks);

head=p2=p1;

for(i=2;i<=n;i++)

{

p1=(struct list_task *)malloc(list_node_size);

printf("please input size of task%d:",i);

scanf("%d",&p1->tasks);

p2->next=p1;

p1->up=p2;

p2=p1;

}

p2->next=NULL;

head->up=NULL;

return head;

}

struct list_task * sort_list(struct list_task * head)

{

int lable;

struct list_task * p1,*p2;

p1=p2=head;

p1=p2->next;

while(p1)

{

if(p1->tasks<p2->tasks)

{

lable=p1->tasks;

p1->tasks=p2->tasks;

p2=p2->up;

while(p2&&lable<p2->tasks)

{

p2->next->tasks=p2->tasks;

p2=p2->up;

}

if(p2)p2->next->tasks=lable;

else head->tasks=lable;

}

p2=p1;

p1=p1->next;

}

head->up=NULL;

return p2;

}

int main(int argc, char **argv)

{

struct list_task *p;

struct tree_node *min_head,*head,*min_p1,*p1,*