Java Spring 金融信贷 deployment split jqgrid NEC bootstrap后台管理模板 后台管理系统模板 nginx视频教程 网赚视频教程 jq延时 软件测试项目实战案例 js键值对数组 java反射方法 mysql更新多个字段 linux 获取系统时间 mysql设置自增初始值 dwf文件怎么转成dwg kubernetes集群 mysql连接 python简易教程 python零基础教程 python位操作 python写入文件 python获取输入 python安装程序 java编程 java集合遍历 java定义接口 java怎么配置环境变量 linux基础教程 摩斯电码翻译器 ps怎么插入表格 图片放大软件 js包含字符串 音乐狂app adobe卸载工具 幽灵行动多少钱 php递归 c语言图书管理系统
当前位置: 首页 > 学习教程  > 编程语言

NOIP2007普及组 纪念品分组(贪心)

2021/1/28 23:22:12 文章标签:

元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。 为使得参加晚会的同学所获得的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过一个给定的整…

元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。

为使得参加晚会的同学所获得的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过一个给定的整数。

为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。

你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。

输入格式
输入文件包含n+2行:

第1行包括一个整数w,为每组纪念品价格之和的上限。

第2行为一个整数n,表示购来的纪念品的总件数。

第3-n+2行每行包含一个正整数Pi,表示所对应纪念品的价格。

输出格式
输出文件仅一行,包含一个整数,即最少的分组数目。

数据范围
1≤n≤30000,
80≤w≤200,
5≤Pi≤w
输入样例:
100 
9 
90 
20 
20 
30 
50 
60 
70 
80 
90
输出样例:
6
将所有物品按价值排序;
从小到大枚举每个物品,每次给当前物品找一个价值尽可能大的
且总价值没有超过上限的“同伴物品”,将两个物品分在一组,
这一步可以使用双指针算法优化到 O(n)。
这样求出的组数就是最小值。
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30010;

int n, m;
int w[N];
bool st[N];//标记是否被用过

int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i ++ ) cin >> w[i];

    sort(w, w + n);

    int res = 0;
    for (int i = 0, j = n - 1; i < n; i ++ )
    {
        if (st[i]) continue;
        while (j >= i && (st[j] || w[i] + w[j] > m)) j -- ;
        st[i] = st[j] = true;
        res ++ ;
    }

    cout << res << endl;
    return 0;
}


本文链接: http://www.dtmao.cc/news_show_650186.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?