首页 > 代码库 > 贪心算法练习：乘船问题
贪心算法练习：乘船问题
/*--------------------------------------------------------------有n个人，第i个的重量为wi，每艘船的最大载重为c，而且最多只能乘两个人。用最少的船装载所有人。输入：第一行两个整数n和c第二行n个整数，分别是wi输出：第一行输出使用船的数量num 第二行到第n+1行每行输出两个数， 分别“人的编号”以及他所乘坐的“船的编号”。 人的编号按输入的顺序从1到n编号。船的编号从1开始编号。 第2行到第n+1行按人的编号从小到大的顺序输出。 思路：考虑最轻的一个人i，他应该和谁一起坐船？假如每个人都无法和他一起坐船，则唯一的方案就是每个人做一艘船了。否则，他应该选择能与他一起乘船的人中最重的一个j。这样的方法是贪心的，他能保证“眼前”的浪费是最少的。 所以，程序中先按体重排序，然后只需用i和j分别表示当前考虑的最轻的人和最重的人。 每次将j往左移动，直到i和j可以一起乘坐一艘船，然后i加1，j减1，并重复上述操作。时间复杂度主要取决于排序。因为上述扫描的复杂度是O(n)级别。 ----------------------------------------------------------------*/
1 #include<stdio.h> 2 #include<stdlib.h> 3 struct person 4 { 5 int id;//人的编号 6 double weight; 7 int shipID;//船的编号 8 }; 9 int cmpQsort1(const void *a,const void *b);//按照struct person 的weight比较a和b的大小。正方向比较。 10 int cmpQsort2(const void *a,const void *b);//按照struct person 的id比较a和b的大小。正方向比较。 11 int main()12 {13 int n,c,i,j,t;//t表示正要分配给第i个人的船的编号 14 int flag=0;//表示没有人体重超重，以至于无法单独乘坐一条船。 15 struct person *a;16 freopen("5.in","r",stdin);17 scanf("%d%d",&n,&c);18 a=(struct person *)malloc(sizeof(struct person)*n);19 for(i=0;i<n;i++)20 {21 scanf("%lf",&a[i].weight);22 a[i].id=i+1;23 a[i].shipID=0;24 }25 qsort(a,n,sizeof(struct person),cmpQsort1);26 t=1;27 for(i=0,j=n-1;i<=j;i++,j--) // 注意分析这里的i<=j. 28 {29 if(a[i].weight>c)30 {31 printf("输入错误！有部分人体重太大，即便是自己一个人坐一条船也坐不下呵呵……\n");32 flag=1;//表示已经发现有人因为体重太大以至于无法单独乘坐一条船。 33 break;34 }35 else36 {37 a[i].shipID=t;38 while(a[i].weight+a[j].weight>c&&j>i) j--;39 a[j].shipID=t;40 t++;41 }42 }43 if(flag==0)44 {45 for(;i<n;i++)//为那些只能考虑单独乘坐一条船的人编排他们乘船的船号 46 {47 if(a[i].shipID==0)//如果这个人还没有编排船号 48 {49 if(a[i].weight<c)50 {51 a[i].shipID=t;52 t++;53 }54 else55 {56 printf("输入错误！有部分人体重太大，即便是自己一个人坐一条船也坐不下呵呵……\n");57 flag=1;//表示已经发现有人因为体重太大以至于无法单独乘坐一条船。58 break; 59 }60 }61 }62 if(flag==0)63 {64 qsort(a,n,sizeof(struct person),cmpQsort2);65 printf("%d\n",t-1);66 for(i=0;i<n;i++)//输出结果 67 {68 printf("%-8.2lf %-3d %-3d\n",a[i].weight,a[i].id,a[i].shipID);69 }70 }71 }72 free(a);73 return 0;74 }75 int cmpQsort1(const void *a,const void *b)//按照struct person 的weight比较a和b的大小。正方向比较。 76 {77 double t=((struct person *)a)->weight - ((struct person *)b)->weight;78 if(t> 1e-5) return 1;79 else if(t< (-1e-5)) return -1;80 else return 0;81 }82 int cmpQsort2(const void *a,const void *b)//按照struct person 的id比较a和b的大小。正方向比较。 83 {84 int t=((struct person *)a)->id - ((struct person *)b)->id;85 if(t> 1e-5) return 1;86 else if(t< (-1e-5)) return -1;87 else return 0;88 }
运行案例
输入：
10 150
80
89
70
30
45
100
120
50
120
40
输出：
6
80.00 1 4
89.00 2 3
70.00 3 5
30.00 4 1
45.00 5 3
100.00 6 2
120.00 7 1
50.00 8 4
120.00 9 6
40.00 10 2
请按任意键继续. . .
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。