思维题，CF 1267J. Just Arrange the Icons

本文主要是介绍思维题，CF 1267J. Just Arrange the Icons，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 1267J - Codeforces

---

二、解题报告

1、思路分析

题意就是我们可以指定screen的size，每个screen可以装size或者size- 1个相同的icon，问我们最少用几个screen就能装完所有icon

显然最坏情况下用n个size为1的screen一定可以装完所有icon，所以问题一定有解

那么我们考虑size最大是多少呢？

假设数目最少的icon为mi个，那么size最大就是mi + 1，再大没法装这种icon了

我们从mi + 1倒序枚举size，取所有合法情况下使用最少的screen数目

我们假设种类一共有k种icon，那么k * mi < sum(cnt[i]) = n

所以时间复杂度上界为O(n)，问题就解决啦

2、复杂度

时间复杂度： O(n) 空间复杂度：O(n)

3、代码详解

​

import sys
from collections import Counterinput = lambda: sys.stdin.readline().strip()write = lambda x: sys.stdout.write(str(x) + '\n')# sys.stdin = open('in.txt', 'r')t = int(input())
while t:t -= 1n = int(input())a = list(map(int, input().split()))st = Counter(a)mi = min(st.items(), key= lambda x: x[1])[1] + 1ret = nwhile mi > 1:s = 0for x, c in st.items():if c % mi == 0:s += c // mielse:if c // mi >= mi - (c % mi) - 1:s += c // mi + 1else:s = 1e9breakret = min(s, ret)mi -= 1print(ret)

这篇关于思维题，CF 1267J. Just Arrange the Icons的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---