纪念品分组(贪心、排序)
2019-10-18 08:35:07来源:博客园 阅读 ()
纪念品分组(贪心、排序)
题目来源:https://www.luogu.org/problem/P1094
贪心算法:先对数组从小到大排序,用 i = 0, j = n - 1
指针指向首尾元素; 如果 a[i] + a[j] ?> w ,则将 a[i]单独作为一组,指针j--
;如果 a[i] + a[j] ≤ w, 则将 a[i] 和 a[j]? 分为一组, 指针 i--, j--
。 如此重复直到 “取完” 所有元素。
题目描述
元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品, 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。
你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。
输入格式
共n+2n+2行:
第11行包括一个整数ww,为每组纪念品价格之和的上上限。
第22行为一个整数nn,表示购来的纪念品的总件数GG。
第33至n+2n+2行每行包含一个正整数P_i(5 \le P_i \le w)Pi?(5≤Pi?≤w)表示所对应纪念品的价格。
输出格式
一个整数,即最少的分组数目。
输入输出样例
输入 #1100 9 90 20 20 30 50 60 70 80 90输出 #1
6
说明/提示
50%的数据满足:1 \le n \le 151≤n≤15
100%的数据满足:1 \le n \le 30000,80 \le w \le 2001≤n≤30000,80≤w≤200
#include<iostream> #include<algorithm> #define N 30000 using namespace std; int a[N]; bool cmp(int x,int y)//重载sort快排,使其从大到小排序 { return x > y; } int main() { int w,n,count = 0; cin >> w >> n; for(int i = 0;i < n;i++) cin >> a[i]; sort(a,a + n,cmp); // for(int i = 0;i < n;i++) // cout << a[i] << " "; int l = 0,r = n - 1;//l为数组的头指针,r为数组的尾指针 while(l <= r)//当两个指针不相遇或刚好相遇时准备结束循环 { if(a[l] + a[r] > w)//当最大数加上最小数大于上限值w时,将最大数单独分为一组,指针后移 { count++; l++; } else//否则满足if条件时将头元素和尾元素放入一组,头指针后移,尾指针前移 { count++; l++; r--; } } cout << count << endl; return 0; } /* 100 9 90 20 20 30 50 60 70 80 90 */
水题不难,最重要的点即为头指针和尾指针的位置。
原文链接:https://www.cnblogs.com/biaobiao88/p/11695108.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Codeforces Round #595 (Div. 3)D1D2 贪心 STL 2019-11-06
- C++贪心算法实现活动安排问题 2019-11-04
- POJ2431 优先队列+贪心 - biaobiao88 2019-11-03
- poj3045 Cow Acrobats (思维,贪心) 2019-10-12
- JZOJ.1153【贪心算法】硬币交换 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash