i791 - pA. 沒有人受傷的世界完成了

🔗 前往 ZeroJudge 原題

題目描述

題目給定 N 個禮物，每個禮物都有一個類別 C_i。有 K 個好友，目標是將每種類別的禮物盡可能平均分配給 K 個好友，且分配數量必須是 K 的整數倍。要求計算在不傷害任何人的情況下，每人最多可以分到幾個禮物。

解題思路

這題的解題思路是統計每種類別禮物的數量，然後對於每種類別，計算可以分配給 K 個好友的禮物數量（取 數量 / K 的整數部分）。最後將所有類別可以分配的禮物數量加總，即為每人最多可以分到的禮物數量。這是一個貪心算法，因為我們盡可能地分配每種類別的禮物。

複雜度分析

• 時間複雜度: O(N + M)，其中 N 是禮物數量，M 是禮物類別的範圍 (在本題中 M = 101)。主要時間花在統計每種類別禮物數量和計算分配數量上。
• 空間複雜度: O(M)，其中 M 是禮物類別的範圍。主要空間花在儲存每種類別禮物數量的陣列 ct 上。

程式碼

#include <iostream>
using namespace std;
int n,k,c,ct[105],ans;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> k;
	for(int i=0;i<n;++i){
		cin >> c;
		++ct[c];
	}
	for(int i=0;i<=100;++i)
		ans+=ct[i]/k;
	cout << ans;
}