网站服务器送一年,wordpress 活动通知,中小企业网站建设客户需求调查问卷,移动应用开发实训报告该题运用贪心算法#xff0c;核心思想是在每次分组时#xff0c;尽可能让价格较小和较大的纪念品组合在一起#xff0c;以达到最少分组的目的。
【算法思路】 输入处理#xff1a;首先读取纪念品的数量n和价格上限w#xff0c;然后依次读取每件纪念品的价格#xff0c;…该题运用贪心算法核心思想是在每次分组时尽可能让价格较小和较大的纪念品组合在一起以达到最少分组的目的。
【算法思路】 输入处理首先读取纪念品的数量n和价格上限w然后依次读取每件纪念品的价格并将其存储在容器vector中 排序使用 sort 函数对纪念品的价格进行从小到大的排序。排序的目的是方便后续使用双指针法能快速找到价格最小和最大的纪念品。 双指针初始化初始化两个指针 left 和 right分别指向价格最小和最大的纪念品。同时初始化分组数量 groups 为 0。 分组过程 ◦ 当 left 小于等于 right 时进入循环 ◦ 如果 left 等于 right说明只剩下一个纪念品将分组数量加 1 并跳出循环。 ◦ 如果价格最小和最大的纪念品价格之和不超过价格上限 w 则将它们分为一组left 指针右移一位right 指针左移一位分组数量加 1。 ◦ 如果价格最小和最大的纪念品价格之和超过价格上限 w 则将价格最大的纪念品单独分为一组right 指针左移一位分组数量加 1。 输出结果循环结束后输出分组的数量。
【代码示例】
#include iostream
#include vector
#include algorithm
using namespace std;int main() {int w, n;// 读取每组纪念品价格上限 w 和纪念品数量 ncin w;cin n;// 使用 n 来初始化 vector 的大小vectorint P(n);// 读取每个纪念品的价格for (int i 0; i n; i) {cin P[i];}// 对纪念品价格从小到大排序sort(P.begin(), P.end());// 双指针法分组int left 0;int right n - 1;// 初始化分组数量为 0int groupCount 0;while (left right) {if (left right) {// 若只剩一个纪念品单独成一组groupCount 1;break;}if (P[left] P[right] w) {// 若最小和最大价格的纪念品能分在一组groupCount 1;left 1;right - 1;} else {// 若不能最大价格的纪念品单独成一组right - 1;groupCount 1;}}// 输出最少的分组数量cout groupCount endl;return 0;
}注意
①双指针一般是整数类型的索引而非指针类型
②使用 n 来初始化 vector 的大小
③将groupCount初始化为0避免未定义行为
