 # 1. 围棋比赛

#### **题目描述**

有 N个人要参加围棋比赛，该比赛要进行 K 场对弈。每个人最多参加两场对弈，最少参加零场对弈。每个人都有一个与其他人不相同的等级（用一个正整数来表示）。
在对弈中，等级高的人必须用黑色的棋子，等级低的人必须用白色的棋子。每个人最多只能用一次黑色的棋子和一次白色的棋子。为增加比赛的可观度，观众希望 K 场对弈中双方的等级差的总和最小。
比如有 7 个选手，他们的等级分别是 30,17,26,41,19,38,18要进行 3 场比赛。最好的安排是选手 2 对选手 7，选手 7 对选手 5，选手 6 对选手 4。此时等级差的总和等于 (18−17)+(19−18)+(41−38)=5 达到最小。
#### **输入描述**

第一行两个正整数 N,K。
接下来有 N 行，第 i 行表示第 i−1个人等级a[i]。
#### **输出描述**

在第一行输出最小的等级差的总和。
#### **输入样例**

1. `7 3`
2. `30`
3. `17`
4. `26`
5. `41`
6. `19`
7. `38`
8. `18`

#### **输出样例**

1. `5`

#### **数据描述**

在 100%的数据中，1≤N≤100000,a[i]≤$$10^9$$,1≤K≤N−1。
#### 参考代码

```cpp
#include<iostream>
#include<algorithm>

using namespace std;

int a[100005];  // 定义数组 a 用于存储输入的 n 个整数，这里假设 n 最大为 100005
int b[100005];  // 定义数组 b 用于存储相邻元素的差值

int main() {
    int n, k;
    // 从标准输入读取两个整数 n 和 k
    // n 表示输入整数的数量，k 表示后续要累加的最小差值的数量
    cin >> n >> k;

    // 循环 n 次，依次从标准输入读取 n 个整数，并存储到数组 a 中
    // 数组下标从 1 开始
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 对数组 a 中的元素进行排序，排序范围是从 a[1] 到 a[n]
    // 使用的是 C++ 标准库中的 sort 函数，排序后数组元素按升序排列
    sort(a + 1, a + 1 + n);

    // 计算数组 a 中相邻元素的差值，并存储到数组 b 中
    // 因为计算相邻元素差值时，最后一个元素没有下一个元素与之计算差值，所以循环到 n - 1
    for (int i = 1; i < n; i++) {
        b[i] = a[i + 1] - a[i];
    }

    // 对数组 b 中的元素进行排序，排序范围是从 b[1] 到 b[n - 1]
    // 排序后数组 b 中的元素按升序排列，即最小的差值在前面
    sort(b + 1, b + n);

    int ans = 0;  // 定义变量 ans 用于存储最终结果，初始化为 0

    // 循环 k 次，将数组 b 中前 k 个最小的差值累加到 ans 中
    for (int i = 1; i <= k; i++) {
        ans += b[i];
    }

    // 输出最终结果 ans，即前 k 个最小差值的和，并换行
    cout << ans << endl;

    return 0;
}
```
#### 解题思路

这道题是关于在围棋比赛中合理安排对阵，使得等级差总和最小的问题。结合题目和给定代码，其解题思路如下：
### 理解比赛规则与目标

明确每个人最多参加两场对阵、最少参加零场，且在对阵中等级高的用黑子，等级低的用白子，每人最多用一次黑子和一次白子 。而我们的目标是让 K 场对阵中双方等级差的总和最小。
### 人员等级排序

把所有人的等级进行排序，不管升序还是降序都可以。排序后能清晰呈现等级的分布情况，方便后续找到等级相近的选手。因为等级相近的选手对阵，产生的等级差相对较小。
### 确定对阵组合

- 基于排序后的等级序列，优先选取相邻或相近等级的选手进行对阵组合。例如，等级排第 1 和第 2 的选手对阵，第 3 和第 4 的选手对阵 ，以此类推。这样能保证每场对阵的等级差较小。
- 但要注意满足每人最多参加两场比赛的限制。在选取对阵组合时，记录每个选手的参赛次数，避免重复安排。

### 计算等级差总和

对确定好的 K 场对阵，分别计算每场对阵双方的等级差，然后将这些等级差相加，得到等级差总和。
### 得出最终答案

经过上述步骤计算得到的等级差总和，就是满足题目条件的最小等级差总和，将其输出即可。
1. # 拼接数字

#### **题目描述**

设有 n 个正整数 a1⋯an，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。
#### **输入描述**

第一行有一个整数，表示数字个数 n。
第二行有 n 个整数，表示给出的 n 个整数 ai。
#### **输出描述**

一个正整数，表示最大的整数
#### **输入样例**

1. `4`
2. `7 13 4 246`

#### **输出样例**

1. `7424613`

#### **数据描述**

对于全部的测试点，保证 1≤n≤20，1≤a≤$$10^9$$
#### 参考代码

```cpp
#include<iostream>
#include<algorithm>

using namespace std;

// 定义一个字符串数组 s，用于存储输入的字符串，最多可存储 25 个字符串
string s[25];
// 定义变量 n，用于存储输入字符串的数量
int n;

// 自定义比较函数 cmp，用于 sort 函数对字符串数组进行排序
// 该函数的目的是确定两个字符串拼接后的字典序大小
// 如果 a 和 b 拼接后的字符串 a + b 的字典序大于 b 和 a 拼接后的字符串 b + a，返回 true
// 这意味着在排序时，a 应该排在 b 前面
bool cmp(string a, string b)
{
    return a + b > b + a;
}

int main(){
    // 从标准输入读取一个整数 n，表示接下来要输入的字符串的数量
    cin >> n;
    // 通过循环依次读取 n 个字符串，并将它们存储到数组 s 中，数组下标从 1 开始
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    // 使用标准库中的 sort 函数对字符串数组 s 进行排序
    // 排序范围是从 s[1] 到 s[n]，使用自定义的比较函数 cmp 来决定排序顺序
    // 排序后，数组 s 中的字符串会按照拼接后字典序最大的方式排列
    sort(s + 1, s + n + 1, cmp);
    // 遍历排序后的字符串数组 s，将每个字符串依次输出
    // 这样输出的结果就是将所有输入字符串拼接成的字典序最大的字符串
    for (int i = 1; i <= n; i++) {
        cout << s[i];
    }
    // 程序正常结束，返回 0
    return 0;
}
```
#### 解题思路

### 问题背景

该程序旨在将输入的 `n` 个字符串进行拼接，使得拼接后的字符串字典序最大。
### 解题思路总结

1. 数据存储
	1. 定义一个大小为 25 的字符串数组 `s` 用于存储输入的字符串，同时定义一个整数 `n` 来记录输入字符串的数量。
2. 自定义比较规则
	1. 实现自定义比较函数 `cmp`，对于两个字符串 `a` 和 `b`，比较 `a + b` 和 `b + a` 的字典序大小。如果 `a + b` 的字典序大于 `b + a`，则认为 `a` 应该排在 `b` 前面。这样做的原因是要让拼接后的字符串整体字典序最大，通过这种比较方式可以确定最优的拼接顺序。
3. 输入处理
	1. 从标准输入读取字符串的数量 `n`。
	2. 通过循环依次读取 `n` 个字符串，并将它们存储到数组 `s` 中，数组下标从 1 开始。
4. 排序操作
	1. 使用 C++ 标准库中的 `sort` 函数对数组 `s` 进行排序，排序范围是从 `s[1]` 到 `s[n]`，排序依据是自定义的比较函数 `cmp`。排序后，数组中的字符串会按照拼接后字典序最大的方式排列。
5. 结果输出
	1. 遍历排序后的数组 `s`，将每个字符串依次输出，这样得到的结果就是将所有输入字符串拼接成的字典序最大的字符串。

### 核心要点


- 关键在于自定义比较函数 `cmp` 的设计，它直接决定了字符串的排序顺序，从而影响最终拼接结果的字典序。
- 利用 `sort` 函数的自定义比较规则功能，简化了排序过程，高效地实现了所需的排序逻辑。

 # 2.闯关小游戏

#### **题目描述**

一年一度的闯关小游戏又开始了，小可报名参赛了，主持人为了表彰大家的勇气，先奖励每个参赛者 m 元。先不要太高兴，因为这些钱还不一定都是你的。接下来主持人宣布了比赛规则：
首先，比赛时间分为 n 个时段，它又给出了很多小游戏，每个小游戏都必须在规定期限 ti前完成。如果一个游戏没能在规定期限前完成，则要从奖励费 m 元中扣去一部分钱 wi，wi 为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!
#### **输入描述**

第一行为 m，表示一开始奖励给每位参赛者的钱；
第二行为 n，表示有 n 个小游戏；
第三行有 n 个数，分别表示游戏 1 到 n 的规定完成期限；
第四行有 n 个数，分别表示游戏 1 到 n 不能在规定期限前完成的扣款数。
#### **输出描述**

输出仅一行，表示小可能赢取最多的钱。
#### **输入样例**

1. `10000`
2. `7`
3. `4 2 4 3 1 4 6`
4. `70 60 50 40 30 20 10`

#### **输出样例**

1. `9950`

#### **数据描述**

对于 100% 的数据，1≤n≤500，1≤m≤5×105，1≤ti≤n，1≤wi≤1000。
#### 参考代码

```
#include<iostream>
#include<algorithm>

using namespace std;

// 定义结构体 node，用于存储每个小游戏的相关信息
struct node {
    int t;    // t 表示游戏的规定完成期限，
    int val;  // val 表示未在规定期限前完成该游戏的扣款数
} a[505];

// m 表示一开始奖励给每位参赛者的钱，n 表示小游戏的数量
int m, n;
// vis 数组用于标记每个时间段是否已经被安排了游戏
// vis[i] 为 1 表示第 i 个时间段已被占用，为 0 表示未被占用
int vis[505]; 

// 自定义比较函数 cmp，用于对小游戏按照未完成时的扣款数从大到小进行排序
// 因为要尽可能减少扣除的钱，所以优先安排扣款多的游戏
bool cmp(node x, node y) {
    return x.val > y.val; 
}

int main() {
    // 从标准输入读取一开始奖励给每位参赛者的钱 m
    cin >> m; 
    // 从标准输入读取小游戏的数量 n
    cin >> n; 

    // 循环读取每个小游戏的规定完成期限
    for (int i = 1; i <= n; i++) {
        cin >> a[i].t; 
    }

    // 循环读取每个小游戏未在规定期限前完成的扣款数
    for (int i = 1; i <= n; i++) {
        cin >> a[i].val; 
    }

    // 使用 sort 函数对小游戏数组 a 按照未完成时的扣款数从大到小进行排序
    // 排序范围是从 a[1] 到 a[n]，排序依据是自定义的比较函数 cmp
    sort(a + 1, a + n + 1, cmp); 

    // ans 用于记录因为未按时完成游戏而扣除的总钱数，初始化为 0
    int ans = 0; 
    // 遍历排序后的小游戏数组
    for (int i = 1; i <= n; i++) {
        // flag 用于标记当前小游戏是否能在规定期限前完成
        // 初始化为 0 表示不能完成
        int flag = 0; 
        // 从当前小游戏的规定完成期限开始往前遍历，尝试找到一个未被占用的时间段
        for (int j = a[i].t; j; j--) { 
            if (vis[j] == 0) {
                // 如果找到未被占用的时间段，标记该时间段已被占用
                vis[j] = 1; 
                // 将 flag 置为 1 表示当前小游戏能在规定期限前完成
                flag = 1; 
                // 找到合适时间段后，跳出内层循环
                break; 
            }
        }
        // 如果遍历完所有可能的时间段后，仍未找到合适的时间段
        // 说明该小游戏无法在规定期限前完成，将其未完成时的扣款数累加到 ans 中
        if (flag == 0) 
            ans += a[i].val; 
    }

    // 用一开始奖励的钱 m 减去因为未按时完成游戏而扣除的总钱数 ans
    // 得到小可能赢取的最多的钱，并将结果输出，然后换行
    cout << m - ans << endl; 

    return 0;
}
```
#### 解题思路

这道题是一个关于在有限时间内合理安排游戏顺序，以获取最大收益的问题。解题的关键在于如何通过对游戏的完成期限和未完成扣款的分析，来规划游戏顺序，从而减少扣款，实现收益最大化。具体解题思路如下：
1. 数据读取与存储
	1. 读取初始奖励金额 `m` 和小游戏的数量 `n`。
	2. 分别读取每个小游戏的规定完成期限 `t_i` 和未在规定期限前完成的扣款数 `w_i`，并使用结构体数组 `a` 来存储这些信息，每个结构体元素对应一个小游戏的两项关键数据。
2. 游戏排序
	1. 由于要使最终获得的钱最多，就需要优先安排未完成扣款数多的游戏，因为如果这些高扣款的游戏未能按时完成，会损失更多的钱。
	2. 因此，使用自定义比较函数 `cmp` 对小游戏数组 `a` 按照未完成时的扣款数从大到小进行排序。
3. 游戏安排与扣款计算
	1. 定义一个数组 `vis` 来标记每个时间段是否已被占用，初始时所有时间段都标记为未占用（值为 `0`）。
	2. 遍历排序后的小游戏数组：
		- 对于每个小游戏，从其规定完成期限开始往前遍历时间，尝试找到一个未被占用的时间段来完成该游戏。
		- 如果找到未被占用的时间段，就将该时间段标记为已占用（`vis[j]=1`），并标记该游戏可以在规定期限前完成（`flag = 1`）。
		- 如果遍历完所有可能的时间段都没有找到合适的未占用时间段，说明该游戏无法在规定期限前完成，将其未完成时的扣款数累加到变量 `ans` 中。
4. 计算最终收益并输出
	1. 用一开始奖励的钱 `m` 减去因为未按时完成游戏而扣除的总钱数 `ans`，得到小可能赢取的最多的钱。
	2. 将计算得到的最终收益输出。

这种解题思路通过合理排序和时间规划，尽可能地减少了因未按时完成游戏而扣除的金额，从而实现了在给定规则下获取最多奖励的目标。

有 N个人要参加围棋比赛，该比赛要进行 K 场对弈。每个人最多参加两场对弈，最少参加零场对弈。每个人都有一个与其他人不相同的等级（用一个正整数来表示）。在对弈中，等级高的人必须用黑色的棋子，等级低的人必须用白色的棋子。每个人最多只能用一次黑色的棋子和一次白色的棋子。为增加比赛的可观度，观众希望 K 场对弈中双方的等级差的总和最小。比如有 7 个选手，他们的等级分别是 30,17,26,41,19,38,18要进行 3 场比赛。最好的安排是选手 2 对选手 7，选手 7 对选手 5，选手 6 对选手 4。此时等级差的总和等于 (18−17)+(19−18)+(41−38)=5 达到最小。

杨校老师课题之备战C++竞赛训练专题--排序与思维提升(贪心思想)

有 N个人要参加围棋比赛，该比赛要进行 K 场对弈。每个人最多参加两场对弈，最少参加零场对弈。每个人都有一个与其他人不相同的等级（用一个正整数来表示）。在对弈中，等级高的人必须用黑色的棋子，等级低的人必须用白色的棋子。每个人最多只能用一次黑色的棋子和一次白色的棋子。为增加比赛的可观度，观众希望 K 场对弈中双方的等级差的总和最小。比如有 7 个选手，他们的等级分别是 30,17,26,41,19,

金牌讲师

编程语言

算法

围棋比赛优化对阵安排，最小化等级差总和；拼接数字实现最大字典序组合；闯关游戏合理安排任务顺序，最大化奖金收益。三个算法问题解析及代码实现，涵盖排序、贪心等核心解题思路。

数据存储

对象存储COS新用户低至1元！


文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

杨校老师课题之备战C++竞赛训练专题--排序与思维提升(贪心思想)-腾讯云开发者社区-腾讯云

杨校老师课题之备战C++竞赛训练专题--排序与思维提升(贪心思想)

杨校老师课题之备战C++竞赛训练专题--排序与思维提升(贪心思想)

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐