C++蓝桥杯实训篇（二）

片头

嗨咯~小伙伴们！今天我们来一起学习算法和贪心思维，准备好了吗？咱们开始咯！

---

第1题  数位排序

对于这道题，我们需要自己写一个排序算法，也就是自定义排序，按照数位从小到大进行排序。

举一个例子呗：假设我们从1~13，对这13个数字进行数位排序

数字	数位和
1	1
2	2
3	3
4	4
5	5
6	6
7	7
8	8
9	9
10	1
11	2
12	3
13	4

从上述表格中，我们可以看出：

①1~13这13个数字，最大的数位和为9。

②1和10的数位和相同，均为1；2和11的数位和相同，均为2；3和12的数位和相同，均为3；4和13的数位和相同，均为4。

③由此可以得出，1~13的排序为：1，10，2，11，3，12，4，13，5，6，7，8，9。第5个数为3。

理解了题意，有什么思路呢？

我们可以先定义num数组，将1~n每个数字对应的数位和存储起来

    int num[10000086];int n;cin >> n;for (int i = 1; i <= n; i++) {int temp = i;while (temp > 0) {int ge = temp % 10;num[i] += ge;			//num数组存储1~n个数的数位和temp = temp / 10;}}

把这n个数字的数位和存储起来后，我们需求出当前这n个数字中最大的数位和。

	//遍历num数组,求出最大的数位和int maxnum = 0;for (int i = 1; i <= n; i++) {maxnum = max(maxnum, num[i]);}

接下来就是重头戏啦：按照数位和从小到大进行排序

外层循环从1~maxnum，表示数位和的取值范围；内层循环从1~n，表示共有n个数参加数位排序

	//按照数位和从小到大进行排序int cnt = 1;//计数器,标记当前数在哪个位置for (int j = 1; j <= maxnum; j++) {for (int i = 1; i <= n; i++) {if (num[i] == j) {res[cnt++] = i;}}}

按照数字和从小到大排序数字：

1. cnt = 1: 计数器，表示res数组中下一个要填充的位置

2. 外层循环 j 从 1 到 maxnum (所有可能的数字和)；内层循环 i 从 1 到 n (所有数字)

3. 如果数字 i 的数字和等于当前 j ，就把 i 放入 res 数组

这样得到的res数组就是按数字和排序的结果，数字和相同的保持原始顺序

 最后输出排序后第m个数字即可。

	//输出第m个元素cout << res[m] << endl;

okk，整体代码如下：

#include<iostream>
using namespace std;//数位排序int n;
int m;int num[10000086];
int res[10000086];int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {int temp = i;while (temp > 0) {int ge = temp % 10;num[i] += ge;			//num数组存储1~n个数的数位和temp = temp / 10;}}//遍历num数组,求出最大的数位和int maxnum = 0;for (int i = 1; i <= n; i++) {maxnum = max(maxnum, num[i]);}//按照数位和从小到大进行排序int cnt = 1;//计数器,标记当前数在哪个位置for (int i = 1; i <= maxnum; i++) {for (int j = 1; j <= n; j++) {if (num[j] == i) {res[cnt++] = j;}}}//输出第m个元素cout << res[m] << endl;return 0;
}

如果对以上代码有疑问的话，不妨看看下面这段文字描述： 

 第2题  封闭图形的个数

对于这道题，咱们可以先定义num数组，把数字0~9的封闭图形的个数存起来。

	int cnt[10]; //全局数组，用于存储每个数字的"圆圈"数量//定义从0~9每个数字中圆圈的个数cnt[0] = 1, cnt[1] = 0, cnt[2] = 0, cnt[3] = 0, cnt[4] = 1;cnt[5] = 0, cnt[6] = 1, cnt[7] = 0, cnt[8] = 2, cnt[9] = 1;

 输入n个数

    const int N = 2e5 + 10;  //定义常量N为200000，作为数组大小int a[N];int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}

接下来是重点：如何将数字按照封闭图形的个数进行排序~

和上一道题类似，只不过是根据当前最后1位数字获取该数字在num数组中的映射。

bool cmp(int a,int b) {int A = a, B = b;			//复制a和b的值，避免修改原值int cnt_a = 0, cnt_b = 0;	//初始化两个数字的圆圈总数//循环计算数字a和b中每个数字位的圆圈数量总和while (A > 0) {int ge = A % 10;		//获取数字的个位数cnt_a += cnt[ge];		//cnt[ge]: 获取该数字的圆圈数量A = A / 10;				//去掉已经处理的个位数}while (B > 0) {int r = B % 10;cnt_b += cnt[r];B = B / 10;}//如果两个数字的圆圈总数相同,按数字本身的大小升序排序//如果圆圈数量不同,按圆圈数量升序排序if (cnt_a == cnt_b) return a < b;     // 圆圈个数相等时比较数值else return cnt_a < cnt_b;			  // 圆圈个数不等时比较圆圈数量
}

欧克，我们写好自定义的排序后，接着就可以利用sort函数进行排序啦~

	/*使用STL的sort函数进行排序a+1：从数组的第1个元素开始a+n+1：到数组的第n个元素结束cmp	：使用自定义的比较函数进行排序*/sort(a + 1, a + n + 1, cmp);for (int i = 1; i <= n; i++) {cout << a[i] << " ";}

okk，本道题完整代码如下：

#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;         //定义常量N为200000，作为数组大小
int cnt[10];                    //全局数组，用于存储每个数字的"圆圈"数量
int a[N];                       //存储输入的数字数组bool cmp(int a,int b) {int A = a, B = b;			//复制a和b的值，避免修改原值int cnt_a = 0, cnt_b = 0;	//初始化两个数字的圆圈总数//循环计算数字a和b中每个数字位的圆圈数量总和while (A > 0) {int ge = A % 10;		//获取数字的个位数cnt_a += cnt[ge];		//cnt[ge]: 获取该数字的圆圈数量A = A / 10;				//去掉已经处理的个位数}while (B > 0) {int r = B % 10;cnt_b += cnt[r];B = B / 10;}//如果两个数字的圆圈总数相同,按数字本身的大小升序排序//如果圆圈数量不同,按圆圈数量升序排序if (cnt_a == cnt_b) return a < b;     // 圆圈个数相等时比较数值else return cnt_a < cnt_b;			  // 圆圈个数不等时比较圆圈数量
}int main() {//定义从0~9每个数字中圆圈的个数cnt[0] = 1, cnt[1] = 0, cnt[2] = 0, cnt[3] = 0, cnt[4] = 1;cnt[5] = 0, cnt[6] = 1, cnt[7] = 0, cnt[8] = 2, cnt[9] = 1;int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}/*使用STL的sort函数进行排序a+1：从数组的第1个元素开始a+n+1：到数组的第n个元素结束cmp	：使用自定义的比较函数进行排序*/sort(a + 1, a + n + 1, cmp);for (int i = 1; i <= n; i++) {cout << a[i] << " ";}return 0;
}

 如果看不懂以上代码，不如看看下面这段描述：

小贴士:

---

第3题  三国游戏

分析题意：

• 三个国家初始得分均为0

• 每个事件会给三个国家带来不同的得分

• 一个国家获胜的条件是该国得分 > 其他两国得分之和

• 目标是找出能让某个国家获胜的最多事件数

对于这道题，我们可以先输入n个事件分别对魏国，蜀国，吴国的得分

    typedef long long ll;	  // 使用long long防止整数溢出const int N = 1e5 + 100;  // 最大事件数int A[N], B[N], C[N];	  // 存储三个国家每个事件的得分cin >> n;//输入原始数据//A、B、C分别存储魏蜀吴3个国家发生对应事件增加的得分for (int i = 1; i <= n; i++) cin >> A[i];  //魏国for (int i = 1; i <= n; i++) cin >> B[i];  //蜀国for (int i = 1; i <= n; i++) cin >> C[i];  //吴国

接下来就该我们来实现当其中1个国家获胜时，最多发生了多少个事件？

首先，我们定义weight[N]数组，用来存储每个事件对某个国家的“纯贡献"

int weight[N];  // 存储每个事件对某个国家的"纯贡献"

我们需要格外注意的是：计算下一个国家的纯贡献值时，必须把当前的weight数组里面的值清空

memset(weight,0,sizeof(weight));  	//将weight数组里面的原始数据清空

对于n个事件，每个事件对某个国家的"纯贡献" = 事件对该国家的得分与其他国家得分之差。

举个例子呗~  假设发生事件 i ,X得4分,Y得2分,Z得1分,可知 4-2-1>0,X获胜

	//计算每个事件对a的纯贡献for (int i = 1; i <= n; i++) {//假设a[i]=7,b[i]=2,c[i]=2,则发生i事件对a的纯贡献是7-2-2=3//可以理解为该发生事件使a比b+c的得分高了3weight[i] = a[i] - b[i] - c[i];}

我们再将每个事件对a的纯贡献，进行从大到小的排序

    bool cmp(int a, int b)	//从大到小进行排序{return a > b;}//将纯贡献按从大到小进行排序sort(weight + 1, weight + n + 1, cmp);

定义变量sum，初始值为0，用来表示累加当前的总贡献。定义变量ans，初始值为0，用来记录可以发生多少事件使a>b+c。

依次循环遍历n个事件对a的纯贡献，用sum累加每个事件对a的纯贡献，如果每次累加的结果使sum>0，那么ans++，直到sum<0，跳出循环。最后返回结果。

	ll sum = 0;     //累加当前的总贡献  int ans = 0;    //记录可以发生多少事件使a>b+cfor (int i = 1; i <= n; i++) {sum += weight[i];		//累加贡献if (sum > 0) ans++;		//累计贡献严格大于0,计数+1else break;				//若不大于0,由于序列递减//后面只会越来越小,直接退出}return ans;					//将事件数返回

此外，我们必须考虑特殊情况：当ans==0时，直接返回-1

	if (ans == 0) return -1;	//1个事件都不能发生,返回-1

okk，关于自定义排序的完整代码如下：

typedef long long ll;	  // 使用long long防止整数溢出const int N = 1e5 + 100;  // 最大事件数
int A[N], B[N], C[N];	  // 存储三个国家每个事件的得分
int weight[N];			  // 存储每个事件对某个国家的"纯贡献"int n;bool cmp(int a, int b)	//从大到小进行排序
{return a > b;
}int solve(int a[], int b[], int c[]) //a获胜,发生最多的事件数
{ll sum = 0; //累加当前的总贡献//将weight数组里面的原始数据清空memset(weight, 0, sizeof(weight));//计算每个事件对a的纯贡献for (int i = 1; i <= n; i++) {//假设a[i]=7,b[i]=2,c[i]=2,则发生i事件对a的纯贡献是7-2-2=3//可以理解为该发生事件使a比b+c的得分高了3weight[i] = a[i] - b[i] - c[i];}//将纯贡献按从大到小进行排序sort(weight + 1, weight + n + 1, cmp);//记录可以发生多少事件使a>b+cint ans = 0;for (int i = 1; i <= n; i++) {sum += weight[i];		//累加贡献if (sum > 0) ans++;		//累计贡献严格大于0,计数+1else break;				//若不大于0,由于序列递减//后面只会越来越小,直接退出}if (ans == 0) return -1;	//1个事件都不能发生,返回-1return ans;					//将事件数返回
}

我们在main函数中调用solve函数，计算魏国，蜀国，吴国能获胜的最多事件数。

魏国获胜的条件是：魏国得分 > 蜀国+吴国得分  -->   a > b + c  -->  a - b - c > 0

蜀国获胜的条件是：蜀国得分 > 魏国+吴国得分  -->   b > a + c  -->  b - a - c > 0

吴国获胜的条件是：吴国得分 > 魏国+蜀国得分  -->   c > a + b  -->  c - a - b > 0

	int ret1 = solve(A, B, C);    //假设魏国获胜,发生最多的事件数int ret2 = solve(B, A, C);    //假设蜀国获胜,发生最多的事件数int ret3 = solve(C, A, B);    //假设吴国获胜,发生最多的事件数

 最后求出最大值即可。

	int MAX = max(ret1, max(ret2, ret3));    //三者取最大值即可cout << MAX << endl;				     //将最终结果输出

okk，这道题的整体代码如下：

//三国游戏
//对于X、Y、Z三个国家,X获胜的条件为 X>Y+Z
//初始时,三者得分均为0
//故X能否获胜完全取决于每个事件对应的得分与其他国家得分之差
//假设发生事件i,X得4分,Y得2分,Z得1分,可知 4-2-1>0,X获胜
//若要求某个国家获胜所发生的最多事件,只需处理每个事件对该国家的纯贡献即可
//所谓纯贡献就是该事件对该国家的得分与其他国家得分之差,只要大于0即说明可获性
//计算每个事件对该国家的纯贡献并从大到小排序,依次累加贡献
//只要总的贡献仍然大于0,就说明当前事件是可以发生的,计数值+1
//依次枚举3个国家,比较出可发生的事件数的最大值即为答案#include <bits/stdc++.h>
using namespace std;typedef long long ll;	  // 使用long long防止整数溢出const int N = 1e5 + 100;  // 最大事件数
int A[N], B[N], C[N];	  // 存储三个国家每个事件的得分
int weight[N];			  // 存储每个事件对某个国家的"纯贡献"int n;bool cmp(int a, int b)	//从大到小进行排序
{return a > b;
}int solve(int a[], int b[], int c[])      //a获胜,发生最多的事件数
{ll sum = 0;                           //初始化累计纯贡献总和（用long long防溢出）memset(weight, 0, sizeof(weight));    //将weight数组里面的原始数据清空//计算每个事件对a的纯贡献for (int i = 1; i <= n; i++) {//假设a[i]=7,b[i]=2,c[i]=2,则发生i事件对a的纯贡献是7-2-2=3//可以理解为该发生事件使a比b+c的得分高了3weight[i] = a[i] - b[i] - c[i];}//将纯贡献按从大到小进行排序sort(weight + 1, weight + n + 1, cmp);//记录可以发生多少事件使a>b+cint ans = 0;for (int i = 1; i <= n; i++) {sum += weight[i];		// 累加当前事件的纯贡献if (sum > 0) ans++;		// 如果累加后总贡献仍为正,则这个事件可以被选择，计数器+1else break;				// 如果总贡献≤0,立即终止循环//（后续事件纯贡献更小，只会让总和更小）}if (ans == 0) return -1;	//1个事件都不能发生,返回-1return ans;					//将事件数返回
}int main() {cin >> n;//输入原始数据//A、B、C分别存储魏蜀吴3个国家发生对应事件增加的得分for (int i = 1; i <= n; i++) cin >> A[i];  //魏国for (int i = 1; i <= n; i++) cin >> B[i];  //蜀国for (int i = 1; i <= n; i++) cin >> C[i];  //吴国int ret1 = solve(A, B, C);    //假设魏国获胜,发生最多的事件数int ret2 = solve(B, A, C);    //假设蜀国获胜,发生最多的事件数int ret3 = solve(C, A, B);    //假设吴国获胜,发生最多的事件数int MAX = max(ret1, max(ret2, ret3));    //三者取最大值即可cout << MAX << endl;				     //将最终结果输出return 0;
}

如果对上述代码有疑问，不妨看看下面的解释~ 

---

 第4题  错误票据

 这道题，需要我们找出重复和缺失的数。因为题目明确告诉我们：读取N行数据，每行数据长度不等。因此，我们可以使用vector容器来动态存储元素。

	vector<int> v;	//动态数组int n;			//输入n行cin >> n;

 我们可以使用for循环来读取这n行数据，将元素尾插到vector容器中。如果遇到'\n'，那么立即停止对这一行的读取。

	for (int i = 1; i <= n; i++)		    //总共输入n行{int x;while (cin >> x)					//读取每行中的每个数字,遇到Ctrl+Z才结束{v.push_back(x);					//将数字添加到动态数组v中if (cin.get() == '\n') break;	//遇到'\n',停止对这一行进行读取}}

接下来我们对vector容器中的元素按照从小到大的顺序排序：

	sort(v.begin(), v.end()); //将所有元素从小到大依次排序

排好序后，我们开始寻找重复和缺失的数字。

重复：2个元素相等

缺失：前一个数字+1不等于后一个数字，也就是非连续的。说明这个数字缺失

	int a = 0;	//用于存储重复的数字int b = 0;	//用于存储缺失的数字for (int i = 0; i < v.size() - 1 ; i++)			// 遍历排序后的数组{if (v[i] == v[i + 1])	  a = v[i];		    // 如果发现相邻数字相同，记录重复数字if (v[i + 1] == v[i] + 2) b = v[i] + 1;		// 如果发现数字间隔为2，记录中间缺失的数字}cout << b << " " << a << endl;					// 输出缺失数字和重复数字

欧克啦，本道题完整代码如下：

#include <bits/stdc++.h>
using namespace std;int main() {vector<int> v;	//动态数组int n;			//输入n行cin >> n;for (int i = 1; i <= n; i++)		//总共输入n行{int x;while (cin >> x)					//读取每行中的每个数字,遇到Ctrl+Z才结束{v.push_back(x);					//将数字添加到动态数组v中if (cin.get() == '\n') break;	//遇到'\n',停止对这一行进行读取}}sort(v.begin(), v.end()); //将所有元素从小到大依次排序int a = 0;	//用于存储重复的数字int b = 0;	//用于存储缺失的数字for (int i = 0; i < v.size() - 1 ; i++)			//遍历排序后的数组{if (v[i] == v[i + 1])	  a = v[i];		    //如果发现相邻数字相同，记录重复数字if (v[i + 1] == v[i] + 2) b = v[i] + 1;		//如果发现数字间隔为2，记录中间缺失的数字}cout << b << " " << a << endl;					//输出缺失数字和重复数字return 0;
}

---

第5题  排个序

这道题，其实是冒泡排序的限制版本。冒泡排序可以任意2个数进行交换，但是这道题有限制条件。

代码如下：

//排个序int a[1010], p[1010], o[1010];//a: 存储待排序数组
//p: 存储允许交换的位置
//o: 一维数组,标记哪些位置允许交换int main() {int n, m;cin >> n >> m;		//输入数组长度n和允许交换的数量m//输入待排序数组for (int i = 1; i <= n; i++) {cin >> a[i];}//输入并标记允许交换的位置for (int i = 1; i <= m; i++) {cin >> p[i];o[p[i]] = 1;	//标记这个位置允许与其下一个位置交换}//单次遍历的冒泡排序for (int i = 1; i < n; i++) // i<n 防止访问a[n+1]越界{if (a[i] > a[i + 1])	//如果需要交换{if (o[i] == 1)		//检查是否允许交换{swap(a[i], a[i + 1]);	//允许则交换}else {cout << "NO";			//不允许则直接失败return 0;}}}cout << "YES";	//所有必要条件都允许,排序成功return 0;
}

---

片尾

今天我们学习了自定义排序和贪心算法。希望看完这篇文章能对友友们有所帮助！！！

求点赞收藏加关注！！！

谢谢大家！！！