ZeroJudge I791: 沒有人受傷的世界完成了

你有 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		在平均分配下，每人最多可以分到的禮物數量。
12 3
1 8 8 4 8 8 4 1 8 4 8 8		3
8 2
99 7 7 7 99 50 50 7		4

解題思路

使用 map<int, int> 來紀錄每一種禮物出現的次數，這邊命名為 MAP。之後跑一個 for (auto it:MAP)，並宣告一個變數 ans 預設為 0，並且每一次將 ans += it.second／K。

範例程式碼－ZeroJudge I791: 沒有人受傷的世界完成了

#include <iostream>
#include <map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, K, ans = 0;
    cin >> N >> K;
    map<int, int>MAP;
    for (int i = 0; i<N; i++) {
        int tmp;
        cin >> tmp;
        MAP[tmp]++;
    }
    for (auto it:MAP) {
        ans += it.second / K;
    }
    cout << ans << "\n";
}

//ZeroJudge I791
//Dr. SeanXD
標籤

相關文章

發佈留言