1143 纪念品分组 2007年NOIP全国联赛普及组
2024-08-21 14:27:52
题目描述 Description
元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。
你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。
输入描述 Input Description
包含n+2行:
第1行包括一个整数w,为每组纪念品价格之和的上限。
第2行为一个整数n,表示购来的纪念品的总件数。
第3~n+2行每行包含一个正整数pi (5 <= pi <= w),表示所对应纪念品的价格。
输出描述 Output Description
仅一行,包含一个整数,即最少的分组数目。
样例输入 Sample Input
100
9
90
20
20
30
50
60
70
80
90
样例输出 Sample Output
6
数据范围及提示 Data Size & Hint
50%的数据满足:1 <= n <= 15
100%的数据满足:1 <= n <= 30000, 80 <= w <= 200
分类标签 Tags 点此展开
将物品按从小到大排序
双向扫描
如果从前往后和从后往前的相加小于最大值
就把他们归为一类
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=;
int a[MAXN];
int main()
{
int w,n;
scanf("%d%d",&w,&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+,a+n+);
int tot=;
for(int i=;i<=n;i++)
{
if(a[i]==-)
continue;
int p=a[i];
int flag=;
for(int j=n;j>=;j--)
{
if(a[j]+p<=w&&a[j]!=-)
{
a[j]=-;
a[i]=-;
tot++;
flag=;
break;
}
}
if(flag==)
{
tot++;
a[i]=-;
}
}
printf("%d",tot);
return ;
}
最新文章
- POCO库——Foundation组件之加解密Crypt
- cmd执行mysql操作
- 20145223《Java程序程序设计》第7周学习总结
- (6) 深入理解Java Class文件格式(五)
- Newtonsoft.Json 序列化和反序列化 时间格式 [转]
- C#中窗体的一些简单运用
- (转)经典线程同步 互斥量Mutex
- scrapy爬取豆瓣电影top250
- Jenkins构建时间Poll Scm的设置
- Cocoa惯性思维调试一例
- vim配置文件(本人喜欢的风格)
- uCos-II中任务的同步与通信
- 【Java每日一题】20170206
- 利用ngnix解决跨域问题
- content-type对照表
- redis水平扩展实践,完全配置,无需代码改动
- editplus5激活码
- 62. 63. Unique Paths 64. Minimum Path Sum
- $digest already in progress 解决办法——续
- POJ2251-Dungeon Master(3维BFS)
热门文章
- C# GUID使用总结
- 获取.net对象的属性集
- POJ1195(二维树状数组)
- eclipse里的Maven插件安装
- Protobuf 文件生成工具 Prototool 命令详解
- jquery、javascript实现(get、post两种方式)跨域解决方法
- ue4-C++中加载一个蓝图类(二)-C++中绑定Blueprint武器
- 51nod1065(set.upper_bound()/sort)
- IT兄弟连 JavaWeb教程 过滤器与监听器经典面试题
- IDEA | 创建启动SpringBoot项目命令