)
计算礼品发送的最小分组数目
华为OD机试真题 - 华为OD上机考试真题 100分题型
华为OD机试真题目录点击查看: 华为OD机试真题题库目录｜机考题库 + 算法考点详解
题目描述
又到了一年的末尾，项目组让小明负责新年晚会的小礼品发放工作。
为使得参加晚会的同事所获得的小礼品价值相对平衡，需要把小礼品根据价格进行分组，但每组最多只能包括两件小礼品，并且每个分组的价格总和不能超过一个价格上限。
为了保证发放小礼品的效率，小明需要找到分组数目最少的方案。
你的任务是写一个程序，找出分组数最少的分组方案，并输出最少的分组数目。
输入描述
第一行数据为分组礼品价格之和的上限
第二行数据为每个小礼品的价格，按照空格隔开，每个礼品价格不超过分组价格和的上限
输出描述
输出最小分组数量
用例1
输入
5 1 2 5输出
2题解
思路：贪心 + 双指针
- 这道题要求
找到分组数目最少的方案, 并且每个分组包含一个或两个礼品，可以推导出要想分组数目越少，就是两个组合的分组个数越多，总分组数量越少。 - 基于上面的分析，要想两个数量分组越多，应该尽可能选择
当前最低价格 + 当前最高价格商品尝试组合，如果当前总价格小于等于限定价格，则将它们组合在一起，如果不能则当前分组选择当前最佳价格对后续两两组合创造更多可能性。 - 根据1 2分析，代码逻辑就是对输入礼品进行升序排序，然后定义
left =0, right = n-1,使用双指针逻辑实现2的逻辑，最终最小分组数。
c++
#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vector<int> split(const string& str, const string& delimiter) { vector<int> result; size_t start = 0; size_t end = str.find(delimiter); while (end != string::npos) { result.push_back(stoi(str.substr(start, end - start))); start = end + delimiter.length(); end = str.find(delimiter, start); } // 添加最后一个部分 result.push_back(stoi(str.substr(start))); return result; } int main() { int maxMoney; cin >> maxMoney; cin.ignore(); string input; getline(cin, input); vector<int> nums = split(input, " "); sort(nums.begin(), nums.end()); int count = 0; int left = 0, right = nums.size() - 1; while (left <= right) { // 剩最后一个 if (left == right) { count++; break; } // 可以选择两个 if (nums[left] + nums[right] <= maxMoney) { left++; } right--; count++; } cout << count; return 0; }JAVA
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int maxMoney = Integer.parseInt(br.readLine().trim()); String input = br.readLine().trim(); String[] parts = input.split(" "); List<Integer> nums = new ArrayList<>(); for (String p : parts) { nums.add(Integer.parseInt(p)); } // 排序 Collections.sort(nums); int count = 0; int left = 0, right = nums.size() - 1; while (left <= right) { // 剩最后一个 if (left == right) { count++; break; } // 可以选择两个 if (nums.get(left) + nums.get(right) <= maxMoney) { left++; } right--; count++; } System.out.println(count); } }Python
importsysdefmain():maxMoney=int(sys.stdin.readline().strip())nums=list(map(int,sys.stdin.readline().strip().split()))nums.sort()count=0left,right=0,len(nums)-1whileleft<=right:# 剩最后一个ifleft==right:count+=1break# 可以选择两个ifnums[left]+nums[right]<=maxMoney:left+=1right-=1count+=1print(count)if__name__=="__main__":main()JavaScript
constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});letlines=[];rl.on("line",line=>lines.push(line));rl.on("close",()=>{letidx=0;constmaxMoney=parseInt(lines[idx++]);constnums=lines[idx++].trim().split(" ").map(Number);nums.sort((a,b)=>a-b);letcount=0;letleft=0,right=nums.length-1;while(left<=right){// 剩最后一个if(left===right){count++;break;}// 可以选择两个if(nums[left]+nums[right]<=maxMoney){left++;}right--;count++;}console.log(count);});Go
packagemainimport("bufio""fmt""os""sort""strconv""strings")funcmain(){in:=bufio.NewReader(os.Stdin)varmaxMoneyintfmt.Fscanln(in,&maxMoney)line,_:=in.ReadString('\n')line=strings.TrimSpace(line)parts:=strings.Split(line," ")nums:=make([]int,0,len(parts))for_,p:=rangeparts{val,_:=strconv.Atoi(p)nums=append(nums,val)}// 排序sort.Ints(nums)count:=0left,right:=0,len(nums)-1forleft<=right{// 剩最后一个ifleft==right{count++break}// 可以选择两个ifnums[left]+nums[right]<=maxMoney{left++}right--count++}fmt.Println(count)}
