每日一题 | 帆船比赛问题

每日一题 | 吃肉饼问题

codeforces的C题，链接：https://codeforces.com/contest/1393/problem/C

这道题非常巧妙，是一道思维题。我们很容易想到，间隔的小距离取决于出现次数多的数。

假设这个数是u，出现了v次。那么我们把它均分到n个空格当中，v个数有v-1个间隔，所以每个间隔大是m = (n - 1) // (v-1)。n-1是因为末尾的元素不产生空格但是会占据位置。我们只需要把剩下的数填入这v-1个空格当中就可以了，它们之间的间隔一定不会小于m。

但还有一个问题是，出现次数达到v的数可能并不只有u，一样可以用上面的方法，只是末尾要额外去掉这些数，有多少个数字出现了v次，就需要减去几。我们假设有y个数字出现了v次。那么答案就是(n - y) // (v - 1) - 1。后要-1是因为每个区间的长度要去掉1才是间隙的距离。

AC代码：

from collections import Counter

t = int(input())
for _ in range(t):
    n = int(input())
    vals = list(map(int, input().split(' ')))
    c = Counter(vals)
    _, num = c.most_common()[]
    if num == n:
        print()
        continue

    for k, v in c.items():
        if v == num:
            n -= 1

    print(n // (num - 1) - 1)

今日问题

帆船比赛问题

有N个选手要参加帆船比赛，帆船比赛规定只能两人组队，并且为了保证公平每一队的选手的体重之和应该一样。现在给定这n个选手的体重，要求将他们尽可能多得凑成队伍，请问多能够凑成多少队？

样例

多t组数据，n小于50

- END -