日常一道算法题。
翻译
年轻的探险者们
有一群探险者，需要去探险，但是大家能力不足，每个人有自己的不足的经验值 e，表示至少需要跟几个人一起出去探险才安全。
现在需要将探险者分组，当然不是所有的探险者必须出门，部分人员可以留在营地。
请问，最多可以多少组人员安全的出去探险。
输入格式
输入整数 t 表示测试用例组数。
每个测试用例输入两行，第一行输入整数 N 表示探险者的人数。第二行输入 N 个整数，用空格分隔，表示每个探险者的不足的经验值。
输出格式
输出整数 T，表示组数。
分析
这道题超时了两次，其实题目很简单，主要是当 T 很大时，python 的 print() 方法消耗了很多时间，我打印出运行时间相差了 2s，也就是print 方法足足花费了 2s。最后将结果拼接成字符串一次性输出，就节约了大量的时间。
主要是贪婪算法，统计每种不足的能力值的个数，然后尽量让数字小的组队，如果有剩余人员则放入下一个数值的组内，这样递推下去可以得到最多的组数。
代码(Python3)
# https://codeforces.com/problemset/problem/1355/B
import sys
import os
import heapq
import math
import time
try:
path = "./file/input.txt"
if os.path.exists(path):
sys.stdin = open(path, 'r')
# sys.stdout = open(r"./file/output.txt", 'w')
except:
pass
t = int(input())
def printd(value):
# print(value)
pass
def case():
n = int(input())
count = [0] * (n + 1)
e = list(map(int, input().split(" ")))
for number in e:
count[number] += 1
result = 0
for index, c in enumerate(count):
if index == 0:
continue
if c >= index:
result += c // index
if c % index != 0 and index < n:
count[index + 1] += c % index
# print(result)
return result
# start = time.time()
result = ""
for _ in range(t):
result += str(case()) + "\n"
print(result, end="")
# print(time.time() - start)
更多代码尽在 https://github.com/Tconan99/Codeforces
by 费城的二鹏 2020.06.16 长春
