QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 4096 MB Total points: 100

#6208. 团队竞赛

Statistics

团队竞赛

你是某大学的编程教练。你的大学正在组建若干支队伍参加编程竞赛。每支参赛队伍由三名程序员组成。

在你的大学里,有 $N$ 名符合条件的程序员,编号从 $0$ 到 $N - 1$。对于每个满足 $0 \le i \le N - 1$ 的 $i$,程序员 $i$ 的技能水平为 $L[i]$。由程序员 $i, j, k$ 组成的队伍,其技能水平为 $\min(L[i], L[j], L[k]) + \max(L[i], L[j], L[k])$。

你只想注册技能水平严格大于 $K$ 的队伍。每名程序员最多只能被分配到一支已注册的队伍中。你希望知道最多可以注册多少支队伍。

实现细节

你需要实现以下函数:

int maximum_teams(int N, int K, int[] L);
  • $N$:程序员的人数。
  • $K$:注册队伍的技能水平限制。
  • $L$:一个长度为 $N$ 的数组,描述了程序员的技能水平。
  • 该函数应返回你可以注册的最多队伍数量。
  • 该函数将被调用恰好一次。

样例

样例 1

考虑以下调用:

maximum_teams(8, 6, [5, 4, 6, 2, 3, 2, 1, 1])

你可以注册一支由程序员 0, 3, 5 组成的队伍(技能水平分别为 5, 2, 2),以及一支由程序员 1, 2, 4 组成的队伍(技能水平分别为 4, 6, 3)。无法注册超过两支队伍。因此,maximum_teams 函数应返回 2。

数据范围

  • $1 \le N \le 100\,000$
  • $1 \le K \le 10^8$
  • $1 \le L[i] \le 10^8$(对于每个 $0 \le i \le N - 1$)

子任务

  1. (6 分) $N \le 3$
  2. (12 分) $N \le 8$
  3. (37 分) $N \le 1000$
  4. (45 分) 无附加限制。

样例评测程序

样例评测程序按以下格式读取输入:

  • 第 1 行:$N \ K$
  • 第 2 行:$L[0] \ L[1] \ \dots \ L[N - 1]$

样例评测程序按以下格式输出你的答案:

  • 第 1 行:maximum_teams 的返回值

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.