网站建设项目流程,wordpress 自动内链,彬县网招聘,php网站内容管理系统[NOIP2007 普及组] 纪念品分组
题目背景
NOIP2007 普及组 T2
题目描述
元旦快到了#xff0c;校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡#xff0c;他要把购来的纪念品根据价格进行分组#xff0c;但每组最多只能包…[NOIP2007 普及组] 纪念品分组
题目背景
NOIP2007 普及组 T2
题目描述
元旦快到了校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡他要把购来的纪念品根据价格进行分组但每组最多只能包括两件纪念品 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品乐乐希望分组的数目最少。
你的任务是写一个程序找出所有分组方案中分组数最少的一种输出最少的分组数目。
输入格式
共 n 2 n2 n2 行
第一行包括一个整数 w w w为每组纪念品价格之和的上限。
第二行为一个整数 n n n表示购来的纪念品的总件数 G G G。
第 3 ∼ n 2 3\sim n2 3∼n2 行每行包含一个正整数 P i P_i Pi 表示所对应纪念品的价格。
输出格式
一个整数即最少的分组数目。
样例 #1
样例输入 #1
100
9
90
20
20
30
50
60
70
80
90样例输出 #1
6提示 50 % 50\% 50% 的数据满足 1 ≤ n ≤ 15 1\le n\le15 1≤n≤15。 100 % 100\% 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。 题意明显排序后直接让最小和最大合成一组即可。
这时候使用两个指针分别指向左右如果左指针所指元素和右指针所指元素无法合成那么就说明右元素无法和任何元素合成最大的这个元素和最小的元素都无法合成那肯定和任何元素都无法合成就让该元素自成一组并且让右指针左移。
#includeiostream
#includealgorithm
using namespace std;
const int N 3e4 10;int a[N];int main() {int w, n; cin w n;for (int i 1; i n; i) {cin a[i];}sort(a 1, a n 1);int pointerofLeft 1, pointerofRight n;int res 0;while (pointerofLeft pointerofRight) { //为什么有等于号因为就算最后左右指针指向同一个元素那这个元素也能自成一组if (a[pointerofLeft] a[pointerofRight] w) {res;pointerofLeft, pointerofRight--;}else {res;pointerofRight--;}}cout res;return 0;
}
