解题思路:
这一题关键在于两个纪念品价格的搭配,在组价格不超出规定价格的前提下,如何分组才能使组数尽量少、组内两个价格之和不大于规定价格?这需要按价格从小到大排序,首先取出价格最小的纪念品,拿它和价格最大的搭配;若价格超出,发现价格最大的纪念品:加当前价格最小的纪念品都超出,和其它纪念品搭配必然超出规定的组价格,所以只能单独分一组;这之后,小价格先不变,大价格应更便宜,才能与小价格搭配,若发现两个一组价格合适,分组成功后,这两个纪念品已进入分组,不再寻找搭配,下次进行分组的小价格更贵、大价格更便宜;以此类推,当小价格与大价格相同时,其它组已分好,当前纪念品成为最后一组,当大价格小于小价格时,没有更多分组。
注意事项:
b指向小价格,t指向大价格,只有在b<t时,才有必要改变b、t,使它们更靠近。
参考代码:
#include<stdio.h> #include<stdlib.h> int a[30001]; int main(){ int y(const void *,const void *); int i,W,n,b,t,c; scanf("%d%d",&W,&n); for(i=0;i<n;i++) scanf("%d",a+i); //输入n个纪念品的价格 qsort(a,n,sizeof(int),y); //按价格从小到大排序 c=b=0;t=n-1; //b和t分别指向小价格和大价格 while(b<=t){ while(a[b]+a[t]>W&&b<t){ //若两个一组价格超出 t--; //小价格不变,大价格应更便宜 c++; //上次的大价格(加当前最小价格都不行)单独分一组 } if(a[b]+a[t]<=W&&b<t){ //若两个一组价格合适 b++; //往后小价格更贵 t--; //往后大价格更便宜 c++; //合适的两个一组 }else if(b==t){ //若小价格与大价格相同 c++; //其它组已分好,最后单独一组 break; } } printf("%d\n",c); return 0; } int y(const void *a,const void *b){ return *(int *)a-*(int *)b; }
0.0分
18 人评分
点我有惊喜!你懂得!浏览:2109 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:604 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:542 |
P1001 (C语言代码)浏览:834 |
C语言训练-大、小写问题 (C语言代码)浏览:644 |
【明明的随机数】 (C语言代码)浏览:839 |
C语言程序设计教程(第三版)课后习题9.2 (C语言代码)浏览:572 |
用筛法求之N内的素数。 (C语言代码)浏览:709 |
简单的a+b (C语言代码)浏览:497 |
快速排序算法1浏览:995 |
不会代码的熊 2022-01-17 19:50:30 |
每组最多两件啊,没问题