2012-C26-team5

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

D: 贪心
读入 n 个数，a[1] .. a[n]，表示每个人的分数，即胜利的场次
首先处理一下这些 a[i]，使得他们的值在 0 到 n - 1 之间（因为总共只有 n 个人，每个人最多进行 n - 1 场比赛），将砍掉的值先记在 ans 里
按 a[i] 从高到低排序，算一下每个人的失败场次 b[i] = n - 1 - a[i]，然后枚举每个人并这样处理：
在其他人中，找出 b[i] 值最高的 a[i] 个人，选出来的人 b[i] 值必须大于 0，若人数不够，则尽可能多取。让 i 和他们打并且 i 获胜，比如打了 cnt[i] 场，并且是和 p[1], p[2] .. p[cnt[i]] 这些人打，选出这些人后将 a[i] -= cnt[i], b[p[j]] -= cnt[i]，并对下一个人继续处理
处理完所有人后，有一部分人剩余一些 a[i] 没有用完，有一部分人剩余一些 b[i] 没有用完，将 ans += (sum(a[i]) + sum(b[i])) / 2 即是答案

D: 贪心

读入 n 个数，a[1] .. a[n]，表示每个人的分数，即胜利的场次

首先处理一下这些 a[i]，使得他们的值在 0 到 n - 1 之间（因为总共只有 n 个人，每个人最多进行 n - 1 场比赛），将砍掉的值先记在 ans 里

按 a[i] 从高到低排序，算一下每个人的失败场次 b[i] = n - 1 - a[i]，然后枚举每个人并这样处理：

在其他人中，找出 b[i] 值最高的 a[i] 个人，选出来的人 b[i] 值必须大于 0，若人数不够，则尽可能多取。让 i 和他们打并且 i 获胜，比如打了 cnt[i] 场，并且是和 p[1], p[2] .. p[cnt[i]] 这些人打，选出这些人后将 a[i] -= cnt[i], b[p[j]] -= cnt[i]，并对下一个人继续处理

处理完所有人后，有一部分人剩余一些 a[i] 没有用完，有一部分人剩余一些 b[i] 没有用完，将 ans += (sum(a[i]) + sum(b[i])) / 2 即是答案