最多的比赛场次--贪心入门？

这里的输出结果为1.

再举个例子

输入 4 2 1 3 2 5 输出 2 说明：如果选择（1，3）那么剩下2和5不能比，只有一场 所以选择（1，2）和（3，5）可以打两场比赛 思路：为了选出之后保证后面还能选，所以每次选都选择体重差值最低的比

审题清楚之后，需要比赛场数最多，那么每一次都选择符合条件(<=k)并且选择这个差值最低的，这样能够保证后面都有组合的机会，每次选择最低即可，这就是贪心，每次选择当前最优。在这里需要注意一个选择过的不能再选，所以需要使用一个visited数组记录当前元素是否已经选过。

下面是我写的一个简陋的实现代码：

#include<iostream> #include<vector> using namespace std; int main() { int n, k; while (cin >> n >> k) { vector<int>input(n); for (int i = 0; i < n; ++i) { cin >> input[i]; } int count = 0; vector<bool>visited(n, false);//记录元素有没有访问过 for (int i = 0; i < n; ++i) { if (visited[i] == 0) {//如果i没有被访问过 int min = INT_MAX;//使用贪心，每次都找最小的，这样才能保证场次最多 int visited_index = -1;//记录已经访问过的下标 for (int j = i + 1; j < n; ++j) { if (visited[j] == 0) {//如果j也没有被访问过 int distance = abs(input[i] - input[j]); if (distance <= k && distance < min) {//如果满足条件的，那么更新min和visited_index min = distance; visited_index = j; } } } if (-1 != visited_index) {//如果访问过其他节点则visited_index不为-1 count++; visited[visited_index] = 1;//设置为1表示该位置已经访问过 } } } cout << count << endl; } }

最重要的是选对了贪心策略，如果有使用过贪心算法经验的对这个题目的贪心策略是一下子能看出来的，可惜偏偏我不是[捂脸]...