題目鏈接： UVA - 11100
題意描述：n個旅行箱，形狀相同，尺寸不同，尺寸小的可以放在尺寸大的旅行箱里。現在要求露在最外面的旅行箱的數量最少的同時滿足一個旅行箱里放的旅行箱的數量最少。求出這樣滿足要求的任意一種方案。
算法分析：首先我們可以確定最少的旅行箱的數量cnt：即n個旅行箱里按照尺寸大小分類（尺寸相同的在同一類），數量最多的那一類的數量。然后把cnt看成有cnt個堆，第二個要求就是要讓這cnt個堆里最大旅行箱數量最小，直接用vector處理即可。
等AC之后突然想到，三個旅行箱尺寸大小為2,2,4，那么就可以把前兩個放在最后一個呀，但答案不是這樣的。-_-
1
#include<iostream>
2
#include<cstdio>
3
#include<cstring>
4
#include<cstdlib>
5
#include<cmath>
6
#include<algorithm>
7
#include<vector>
8
#define
inf 0x7fffffff
9
using
namespace
std;
10
const
int
maxn=
10000
+
10
;
11
const
int
M =
1000000
+
10
;
12
13
int
n,an[maxn];
14
int
vis[M],num[maxn];
15
vector<
int
>
vec[maxn];
16
17
int
main()
18
{
19
int
ok=
0
;
20
while
(scanf(
"
%d
"
,&n)!=EOF &&
n)
21
{
22
if
(ok) printf(
"
\n
"
);
23
ok=
1
;
24
memset(vis,
0
,
sizeof
(vis));
25
for
(
int
i=
0
;i<maxn ;i++
) vec[i].clear();
26
int
cnt=
0
,maxSize=
0
;
27
for
(
int
i=
1
;i<=n ;i++
)
28
{
29
scanf(
"
%d
"
,&
an[i]);
30
vis[an[i] ]++
;
31
cnt=
max(cnt,vis[an[i] ]);
32
maxSize=
max(maxSize,an[i]);
33
}
34
sort(an+
1
,an+n+
1
);
35
int
c=
0
;
36
for
(
int
i=
1
;i<=n ;i++
)
37
{
38
vec[c].push_back(an[i]);
39
c=(c+
1
)%
cnt;
40
}
41
printf(
"
%d\n
"
,cnt);
42
for
(
int
i=
0
;i<cnt ;i++
)
43
{
44
int
k=
vec[i].size();
45
printf(
"
%d
"
,vec[i][
0
]);
46
for
(
int
j=
1
;j<k ;j++) printf(
"
%d
"
,vec[i][j]);
47
printf(
"
\n
"
);
48
}
49
}
50
return
0
;
51
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
