[NOIP2007 普及組] 紀(jì)念品分組
題目描述
元旦快到了，校學(xué)生會(huì)讓樂樂負(fù)責(zé)新年晚會(huì)的紀(jì)念品發(fā)放工作。為使得參加晚會(huì)的同學(xué)所獲得 的紀(jì)念品價(jià)值相對(duì)均衡，他要把購來的紀(jì)念品根據(jù)價(jià)格進(jìn)行分組，但每組最多只能包括兩件紀(jì)念品， 并且每組紀(jì)念品的價(jià)格之和不能超過一個(gè)給定的整數(shù)。為了保證在盡量短的時(shí)間內(nèi)發(fā)完所有紀(jì)念品，樂樂希望分組的數(shù)目最少。
你的任務(wù)是寫一個(gè)程序，找出所有分組方案中分組數(shù)最少的一種，輸出最少的分組數(shù)目。
輸入格式
共 n + 2 n+2 n+2 行：
第一行包括一個(gè)整數(shù) w w w，為每組紀(jì)念品價(jià)格之和的上限。
第二行為一個(gè)整數(shù) n n n，表示購來的紀(jì)念品的總件數(shù) G G G。
第 3 ～ n + 2 3\sim n+2 3～n+2 行每行包含一個(gè)正整數(shù) P i P_i Pi? 表示所對(duì)應(yīng)紀(jì)念品的價(jià)格。
輸出格式
一個(gè)整數(shù)，即最少的分組數(shù)目。
樣例 #1
樣例輸入 #1
100
9
90
20
20
30
50
60
70
80
90
樣例輸出 #1
6
提示
50 % 50\% 50% 的數(shù)據(jù)滿足： 1 ≤ n ≤ 15 1\le n\le15 1≤n≤15。
100 % 100\% 100% 的數(shù)據(jù)滿足： 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。文章來源：http://www.zghlxwxcb.cn/news/detail-632229.html
每天最愜意的就是聽歌喝茶切水題，普及題小小的也很可愛
文章來源地址http://www.zghlxwxcb.cn/news/detail-632229.html
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[30004];
int main()
{
cin>>m;
cin>>n;
int ans=0;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
for(int i=1,j=n;i<=j;j--)
{
if(a[i]+a[j]>m)ans++;
else if(a[i]+a[j]<=m)ans++,i++;
}
cout<<ans<<endl;
return 0;
}
到了這里，關(guān)于[NOIP2007 普及組] 紀(jì)念品分組的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[NOIP2004 普及組] FBI 樹 隊(duì)列解法](https://imgs.yssmx.com/Uploads/2024/02/472143-1.png)
![搜索？——P3956 [NOIP2017 普及組] 棋盤](https://imgs.yssmx.com/Uploads/2024/02/429533-1.png)
![#P0999. [NOIP2008普及組] 排座椅](https://imgs.yssmx.com/Uploads/2024/02/618805-1.png)
