解题思路:
    初步分析:题目中说明每组最多两件,所以为了满足分组数量最小,就需要尽量使“一组两个”最多,容易想到解决办法,是尽可能地使两个的和逼近价格上限。

    解决办法:将商品依照价格从高到低排序,使用一个简易的数组,模拟作为栈,依次遍历排序后的价格数组,如果 栈空 或者 栈顶元素与当前获取到的价格之和大于价格上限 就将当前价格(商品)入栈, 反之如果可以分至一组,就出栈,组数加一;遍历完所有商品后,将栈中剩余的价格(商品)单独成一组。

    部分原理: 因为进行栈操作前,数组已经降序排列,那么依次遍历得到的商品价格必然从高到低,即栈顶元素对应价格低于栈内所有商品价格,当最新遍历得到的商品价格可以和栈顶元素分为一组时,在此之后的商品价格又等于或者小于该值,所以当前值不管是否可以和栈内元素相加小于上限,后面的商品价格与栈内元素之和小于上限的可能性都更大,从而便捷的尽可能满足多的。【总的来说就是通过是最小的尽可能地和更大的分到一组,使用栈只是一个小辅助。】
注意事项:

参考代码:di


#include<stdio.h>

#include<stdlib.h>

#include<math.h>


int cmp(void*a,void*b){ return (*(int*)b-*(int*)a);} // qsort的比较函数

int main()

{

     int max; // 价格和的上限

     int num; // 商品数量

     scanf("%d %d",&max,&num);

     int array[num]; // 记录价格的数组

    int cnt = 0;   


     int stack[num+1];   int top=0; // 一个简易的栈

    

     for(int i = 0; i < num; i++) scanf("%d",&array[i]);

     qsort(array,num,sizeof(int),cmp); // 降序排列

    

     int index = 0;     

    int tmp; // 临时变量   

    while(index<num) {

        tmp = array[index++]; // 临时使用tmp 记录array[index]的值

        if(top == 0 || tmp + stack[top-1] > max) 

            stack[top++] = tmp; // 如果栈空或者栈顶元素不可以和当前元素分至一组, 入栈

        else if(tmp + stack[top-1] <= max) {cnt+=1;top--;} // 栈顶和当前数可以分为一组,出栈

    }

     cnt += top; // 统计栈内剩余元素量,加到总组数上


     printf("%d\n",cnt);

     return 0;

}



点赞(0)
 

0.0分

0 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论