P1094 [NOIP2007 普及组] 纪念品分组——贪心算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了P1094 [NOIP2007 普及组] 纪念品分组——贪心算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1471字,纯文字阅读大概需要3分钟。
内容图文
![P1094 [NOIP2007 普及组] 纪念品分组——贪心算法](/upload/InfoBanner/zyjiaocheng/597/b28b4ed3af1a4fb9b4c3df78aac3e2a2.jpg)
题目描述
元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品, 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。
你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。
输入格式
共 n + 2 n+2 n+2 行:
第一行包括一个整数 w w w,为每组纪念品价格之和的上上限。
第二行为一个整数 n n n,表示购来的纪念品的总件数 G G G。
第 3 ~ n + 2 3\sim n+2 3~n+2 行每行包含一个正整数 P i P_i Pi? 表示所对应纪念品的价格。
输出格式
一个整数,即最少的分组数目。
输入输出样例
输入
100
9
90
20
20
30
50
60
70
80
90
输出
6
说明/提示
50 % 50\% 50% 的数据满足: 1 ≤ n ≤ 15 1\le n\le15 1≤n≤15。
100% 的数据满足: 1 ≤ n ≤ 3 × 1 0 4 1\le n\le3\times10^4 1≤n≤3×104 , 80 ≤ w ≤ 200 80\le w\le200 80≤w≤200, 5 ≤ P i ≤ w 5 \le P_i\le w 5≤Pi?≤w
贪心就行,排完序找最小,最大和最小分组
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int main()
{
int t, n;
cin >> t >> n;
int *arr = new int[n + 10];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
sort(arr, arr + n);
// cout << "-----" << endl;
// for (int i = 0; i < n; i++)
// cout << arr[i] << endl;
// cout << "-----" << endl;
int l = 0, r = n - 1;
int cnt = 0;
while (l <= r)
{
// printf("l = %d r = %d cnt = %d arr[%d]=%d arr[%d]=%d\n", l, r, cnt, l, arr[l], r, arr[r]);
if (arr[l] + arr[r] <= t)
{
cnt += 1;
l++;
r--;
}
else
{
cnt++;
r--;
}
}
cout << cnt << endl;
return 0;
}
AC
内容总结
以上是互联网集市为您收集整理的P1094 [NOIP2007 普及组] 纪念品分组——贪心算法全部内容,希望文章能够帮你解决P1094 [NOIP2007 普及组] 纪念品分组——贪心算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。