首页 > 其他分享 >P1094 [NOIP2007 普及组] 纪念品分组

P1094 [NOIP2007 普及组] 纪念品分组

时间:2024-09-23 20:16:54浏览次数:11  
标签:NOIP2007 int le P1094 纪念品 分组 一个组 贪心

[NOIP2007 普及组] 纪念品分组

题目背景

NOIP2007 普及组 T2

题目描述

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

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

输入格式

共 $n+2$ 行:

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

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

第 $3\sim n+2$ 行每行包含一个正整数 $P_i$ 表示所对应纪念品的价格。

输出格式

一个整数,即最少的分组数目。

样例 #1

样例输入 #1

100 
9 
90 
20 
20 
30 
50 
60 
70 
80 
90

样例输出 #1

6

提示

$50%$ 的数据满足:$1\le n\le15$。

$100%$ 的数据满足:$1\le n\le3\times10^4$,$80\le w\le200$,$5 \le P_i \le w$。


贪心

重在证明,虽然AC了证明还是模糊

贪心策略:

1.首先对所有物品的价值从小到大进行排序

2.用两个指针,一个指向前端,另一个指向后端;

3.最小的匹配最大的时候分组数最小

4.当 $a_i + a_j > w$时,j--;

说明后面数太大了,只能独立作为一个组

5.当 $a_i + a_j <= w$ 时,i++, j--;

两个数作为一个组

证明:

分情况进行讨论:

首先贪心得到的解是一种可行方案,而最后的最优解是所有可行方案中的最小值,
因此可以证明出 最优解 <= 贪心得到的解

存在最优解S ,他不是按照贪心步骤得到的;

1.$a_i + a_j > w$ 时,由于从小到大进行了排序 $a_i$ 是当前最小的,说明$a_j$不能与其他任何$a_k$为一组,$i < k < j $,因此$a_j$只能独立分组;

2.$a_i + a_j <= w$ ,而最优解中并不是$a_i与a_j$ 一组;

(1)$a_j$ 是独立分组的,并且$a_i$也是独立分组的时候,由于$a_i + a_j <= w$,将它俩合并为同一个组,这时分组数-1,这里可以证明出最优解 >= 贪心得到的解

到这一步我们可知贪心得到的解就是最优解。

进一步说明:
已知 $i < k < j$,

(2)$a_j$ 单独一组,$a_i 与 a_k$ 一组,将$a_i$与$a_k4拆分,再把$a_i$与$a_j$合并,这是分组数不变

(3)$a_j与a_k$ 一组,$a_i$单独一个组,这时候交换$a_i,a_k$, 分组数仍不变

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 3e4 + 10;

int w,n;
int a[N];
int ans;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> w >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	sort(a + 1, a + 1 + n);
	int i = 1,j = n;
	while(i <= j){
		if(a[i] + a[j] > w) {
			ans ++;   //单独作为一个组
			j--; 
		}
		else{
			ans ++;  //两件物品一起作为一个组
			i++;
			j--; 
		}
	}
	cout << ans << endl;
	return 0;
}

标签:NOIP2007,int,le,P1094,纪念品,分组,一个组,贪心
From: https://www.cnblogs.com/ltphy-/p/18427791

相关文章

  • 洛谷 P1093 [NOIP2007 普及组] 奖学金
    [NOIP2007普及组]奖学金题目背景NOIP2007普及组T1题目描述某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前555名学生发奖学金。期末,每个学生都......
  • 【题解】【结构体排序】——[NOIP2007 普及组] 奖学金
    【题解】【结构体排序】——[NOIP2007普及组]奖学金[NOIP2007普及组]奖学金题目背景题目描述输入格式输出格式输入输出样例输入#1输出#1输入#2输出#21.题意解析2.AC代码[NOIP2007普及组]奖学金通往洛谷的传送门题目背景NOIP2007普及组T1题目描述某......
  • P2825 [HEOI2016/TJOI2016] 游戏 与 P10945 Place the Robots
    本文中的机器人同炸弹,主要是题目描述不同,两道题目做法是本质相同的。思路:先说一下没有墙怎么办,那么当一个位置放了机器人之后,这个机器人所在的行和列是不能继续放置的。那么发现行和列几乎是独立的,考虑建二分图,若\((i,j)\)能放一个机器人,那么给\(i\toj\)建一条边。那么......
  • dp(2019csp-j纪念品)
    #include<bits/stdc++.h>usingnamespacestd;intn,T,a[101][101],v[101],f[10010];voidsolve(intd1,intd2){memset(f,0,sizeof(int)*(v[d1]+1));for(inti=1;i<=n;i++){intc=a[d1][i],w=a[d2][i];......
  • 洛谷——P1093 [NOIP2007 普及组] 奖学金
    题目背景NOIP2007普及组T1题目描述某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前555名学生发奖学金。期末,每个学生都有......
  • 洛谷P1098 [NOIP2007 提高组] 字符串的展开
    题目链接:-P1098[NOIP2007提高组]字符串的展开题目叙述:[NOIP2007提高组]字符串的展开题目描述在初赛普及组的“阅读程序写结果”的问题中,我们曾给出一个字符串展开的例子:如果在输入的字符串中,含有类似于d-h或者4-8的字串,我们就把它当作一种简写,输出时,用连续递增的字......
  • 纪念品(2019CSP-J)
    题目描述    小伟突然获得一种超能力,他知道未来T天N种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量,以及卖出一个该纪念品换回的金币数量。    每天,小伟可以进行以下两种交易无限次:任选一个纪念品,若手上有足够金币,以当日价格购买该纪念品;......
  • P1093 [NOIP2007 普及组] 奖学金【排序】
    [NOIP2007普及组]奖学金题目背景NOIP2007普及组T1题目描述某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前555名学生发奖学金。期末,每个学生都......
  • [NOIP2007 普及组] 纪念品分组
    传送锚点:www.luogu.com.cn题目背景NOIP2007普及组T2题目描述元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过......
  • P1098 [NOIP2007 提高组] 字符串的展开
    注意三种情况: 1.开头结尾的-,例:-abc--2.-两侧必须同为小写字母或同为数字例;A-a3.对数字不能进行大小写转换#include<iostream>#include<stdio.h>#include<algorithm>#include<string>#include<cmath>#include<algorithm>#defineFor(i,j,n)for(inti=j......