【NOIP普及组】纪念品分组

- - C语言实现
  - C++实现
  - Java实现
  - Python实现

💐The Begin💐点点关注，收藏不迷路💐

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入

输入包含n+2行：
第1行包括一个整数w，为每组纪念品价格之和的上限。
第2行为一个整数n，表示购来的纪念品的总件数。
第3~n+2行每行包含一个正整数pi (5 <= pi <= w)，表示所对应纪念品的价格。

输出

输出仅一行，包含一个整数，即最少的分组数目。

样例输入

样例输出

提示

【限制】50%的数据满足：1 <= n <= 15
100%的数据满足：1 <= n <= 30000, 80 <= w <= 200

根据实际输入的纪念品数量 n 来动态分配价格数组的空间,在 main 函数中通过 malloc 函数根据输入的 n 动态分配了价格数组 prices 的空间，并在程序结束前通过 free 函数释放了该动态分配的内存，以避免内存泄漏。

C语言实现

#include <stdio.h>
#include <stdlib.h>// 比较两个整数并返回较大值
int max(int a, int b) {return (a > b)? a : b;
}// 比较两个整数并返回较小值
int min(int a, int b) {return (a < b)? a : b;
}// 比较函数，用于qsort，按照升序排列
int compare(const void * a, const void * b) {return ( *(int*)a - *(int*)b );
}// 对纪念品进行分组，返回最少的分组数目
int groupSouvenirs(int w, int n, int *prices) {int count = 0;int i = 0, j = n - 1;// 使用qsort对纪念品价格数组进行排序，以便后续分组操作qsort(prices, n, sizeof(int), compare);// 从价格最低和最高的纪念品开始尝试分组while (i <= j) {if (prices[i] + prices[j] <= w) {// 如果最低价格和最高价格的纪念品能组成一组，就将它们分组，并移动指针i++;j--;} else {// 如果不能组成一组，就只将最高价格的纪念品单独分组，移动指针j--;}count++;}return count;
}int main() {int w, n;// 读取每组纪念品价格之和的上限scanf("%d", &w);// 读取购来的纪念品的总件数scanf("%d", &n);// 动态分配价格数组的空间int *prices = (int *)malloc(n * sizeof(int));if (prices == NULL) {printf("内存分配失败！\n");return 1;}// 读取每件纪念品的价格for (int i = 0; i < n; i++) {scanf("%d", &prices[i]);}// 调用函数进行分组并输出最少的分组数目printf("%d\n", groupSouvenirs(w, n, prices));// 释放动态分配的内存空间free(prices);return 0;
}

C++实现

#include <iostream>
#include <algorithm>
#include <vector>// 对纪念品进行分组，返回最少的分组数目
int groupSouvenirs(int w, int n, const std::vector<int>& prices) {int count = 0;int i = 0, j = n - 1;// 对纪念品价格向量进行排序，以便后续分组操作std::vector<int> sortedPrices = prices;std::sort(sortedPrices.begin(), sortedPrices.end());// 从价格最低和最高的纪念品开始尝试分组while (i <= j) {if (sortedPrices[i] + sortedPrices[j] <= w) {// 如果最低价格和最高价格的纪念品能组成一组，就将它们分组，并移动指针i++;j--;} else {// 如果不能组成一组，就只将最高价格的纪念品单独分组，移动指针j--;}count++;}return count;
}int main() {int w, n;std::vector<int> prices;// 读取每组纪念品价格之和的上限std::cin >> w;// 读取购来的纪念品的总件数std::cin >> n;// 读取每件纪念品的价格for (int i = 0; i < n; i++) {int price;std::cin >> price;prices.push_back(price);}// 调用函数进行分组并输出最少的分组数目std::cout << groupSouvenirs(w, n, prices) << std::endl;return 0;
}

Java实现

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;// 对纪念品进行分组，返回最少的分组数目
public class Main {public static int groupSouvenirs(int w, int n, ArrayList<Integer> prices) {int count = 0;int i = 0, j = n - 1;// 对纪念品价格列表进行排序，以便后续分组操作Collections.sort(prices);// 从价格最低和最高的纪念品开始尝试分组while (i <= j) {if (prices.get(i) + prices.get(j) <= w) {// 如果最低价格和最高价格的纪念品能组成一组，就将它们分组，并移动指针i++;j--;} else {// 如果不能组成一组，就只将最高价格的纪念品单独分组，移动就针j--;}count++;}return count;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int w = scanner.nextInt();int n = scanner.nextInt();ArrayList<Integer> prices = new ArrayList<>();// 读取每件纪念品的价格for (int i = 0; i < n; i++) {prices.add(scanner.nextInt());}// 调用函数进行分组并输出最少的分组数目System.out.println(groupSouvenirs(w, n, prices));scanner.close();}
}

Python实现

def groupSouvenirs(w, n, prices):count = 0i, j = 0, len(prices) - 1# 对纪念品价格列表进行排序，以便后续分组操作prices.sort()# 从价格最低和最高的纪念品开始尝试分组while i <= j:if prices[i] + prices[j] <= w:# 如果最低价格和最高价格的纪念品能组成一组，就将它们分组，并移动指针i += 1j -= 1else:# 如果不能组成一组，就只将最高价格的纪念品单独分组，移动指针j -= 1count += 1return countw = int(input())
n = int(input())
prices = [int(input()) for _ in range(n)]# 调用函数进行分组并输出最少的分组数目
print(groupSouvenirs(w, n, prices))