i791. pA. 沒有人受傷的世界完成了
標籤 : 陣列
通過比率 : 94人/103人 ( 91% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-09-15 13:09

內容

你有 N 個禮物和 K 個好友,
對於這 N 個禮物,每個禮物都擁有所屬禮物類別 Ci

 

為了避免朋友間因分配不均,互相比較而受傷害,
你決定將這 N 個禮物依照類別,對於每種類別盡可能地平均分配。
也就是對於每種類別的禮物,都只會取 K 的整數倍數量做分配。

 

舉例來說,假設 N = 12, K = 3,
N 個禮物所屬類別分別為 {1, 8, 8, 4, 8, 8, 4, 1, 8, 4, 8, 8}
計算後共有 2 個(類別1)的禮物、3 個(類別4)的禮物、7 個(類別8)的禮物

 

對於三個人,每人最多可以分到,
0 個(類別1)的禮物、1 個(類別4)的禮物、2 個(類別8)的禮物
也就是每人最多可分到 0 + 1 + 2 = 3 個禮物

 

給定 N, K 和禮物類別序列 {C0, C1, ..., CN-1}
在不傷害任何人的情況下,請協助計算每人最多可以分到幾個禮物?

 

就這樣,沒有人受傷(只有你的腦力受傷)的世界完成了

輸入說明

第一行有兩個正整數 N, K,代表禮物總數和好友數量
1 ≤ N ≤ 106
1 ≤ K ≤ max(2, N/50)

第二行由左至右有 N 個整數 Ci,代表禮物所屬類別
0 ≤ Ci ≤ 100

輸出說明

在平均分配下,每人最多可以分到的禮物數量

範例輸入 #1
12 3
1 8 8 4 8 8 4 1 8 4 8 8
範例輸出 #1
3
範例輸入 #2
8 2
99 7 7 7 99 50 50 7
範例輸出 #2
4
測資資訊:
記憶體限制: 512 MB
提示 :

30%:N ≤ 100
10%:Ci 只會有 0, 1, 2
60%:無特別限制 

標籤:
陣列
出處:
111學年度hgsh校內賽 [管理者: mushroom.cs9 ... (mushroom) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
41441 toseanlin@gm ... (Dr. SeanXD) i791
C++詳解-Map
71 2024-07-27 10:35
32188 mushroom.cs9 ... (mushroom) i791
398 2022-09-20 09:54