左嘉


私信TA

用户名:zuojia

访问量:85847

签 名:

Jz

等  级
排  名 5
经  验 33935
参赛次数 226
文章发表 72
年  龄 40
在职情况 在职
学  校 北京理工大学
专  业

  自我简介:

解题思路:
这一题关键在于两个纪念品价格的搭配,在组价格不超出规定价格的前提下,如何分组才能使组数尽量少、组内两个价格之和不大于规定价格?这需要按价格从小到大排序,首先取出价格最小的纪念品,拿它和价格最大的搭配;若价格超出,发现价格最大的纪念品:加当前价格最小的纪念品都超出,和其它纪念品搭配必然超出规定的组价格,所以只能单独分一组;这之后,小价格先不变,大价格应更便宜,才能与小价格搭配,若发现两个一组价格合适,分组成功后,这两个纪念品已进入分组,不再寻找搭配,下次进行分组的小价格更贵、大价格更便宜;以此类推,当小价格与大价格相同时,其它组已分好,当前纪念品成为最后一组,当大价格小于小价格时,没有更多分组。

注意事项:
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 人评分

  评论区

如果我输入:
100
9
2
3
4
5
6
7
8
99
你的程序输出5
但真正的最小分组是2
因为2+3+...+8 < 100
所以你的思路不太对吧。
2021-02-03 11:28:55
如果我输入:
100
2
3
4
5
6
7
8
99
你的程序输出5
但真正的最小分组是2
因为2+3+...+8 < 100
所以你的思路不太对吧。
2021-02-03 11:28:09
  • «
  • 1
  • »