349
WIKIOI 1143 紀念品分組
1143 紀念品分組
題目描述 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
思路：將要分發的物品按照從大到小的順序排序，之後第一個去和最後一個相加，如果小於規定數n，且沒有被分過組，則分類總數sum加1，如果不行，那往前一個數一定比最後一個數大，就不用再判斷了，也就是第一個數隻能單獨分一個組，繼續第二個數和最後一個未分組的數比（分過組的標記好。），直到所有數都被分組即可
例如樣例給的數據：90,90,80,70,60,50,30,20,20（排序後）,一知分組不能超過100
首先，90+20>100，不行，90單獨分一組，sum=1；
第二，90同理單獨一組，sum=2；
第三，80+20==100,那麼80和20一組，sum=3；
第四，70+20<100,70和20一組，sum=4；
第五，60+30<100,60和30一組，sum=5；
第六，由於其他所有數都參與了分組，隻剩下50自己，所以它自己一組，sum=6；
所以答案為6
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct node
{
int flag;
int num;
}a[30010];
int cmp(node x,node y)
{
if(x.num!=y.num) return x.num>y.num;
}
int main()
{
int i,j,n,m,sum,x;
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
for(i=0;i<m;i++)
scanf("%d",&a[i].num);
sort(a,a+m,cmp);
sum=0;
for(i=0;i<m;i++)
{
x=0;
for(j=m-1;j>=0;j--)
{
if(j==i)
continue;
if(a[i].num+a[j].num<=n&&a[j].flag==0&&a[i].flag==0)
{
a[j].flag=1;
a[i].flag=1;
sum++;
x=1;
break;
}
}
if(x==0&&a[i].flag==0){ sum++;}
}
printf("%d\n",sum);
return 0;
}
最後更新：2017-04-03 12:55:21