翻译

年轻的探险者们

有一群探险者，需要去探险，但是大家能力不足，每个人有自己的不足的经验值 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 长春