vector习题

完数和盈数

题目

完数VS盈数_牛客题霸_牛客网

一个数如果恰好等于它的各因子(该数本身除外)之和，如：6=3+2+1。则称其为“完数”；若因子之和大于该数，则称其为“盈数”。 求出2到60之间所有“完数”和“盈数”。

输入描述：

题目没有任何输入。

输出描述：

输出2到60之间所有“完数”和“盈数”，并以如下形式输出： E: e1 e2 e3 ......(ei为完数) G: g1 g2 g3 ......(gi为盈数) 其中两个数之间要有空格，行尾不加空格。

代码

思路：

定义一个函数求出某个数的因数之和sum

定义两个数组wan和yin

遍历2到60，把这些数和对应的sum对比，从而符合条件的数加到wan和yin两个数组中。再打印输出。

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<vector>
using namespace std;
​
/*
参数：int num
返回值：各参数之和 int
处理：求某个数的因数之和
*/
int FactorNum(int num) {int sum = 0;for (int i = 1; i < num; i++) {if (num % i == 0) {sum += i;}}return sum;
}
​
int main() {vector<int> wan;vector<int> yin;for (int i = 2; i <= 60; i++) {/*若因子之和等于该数，则称其为“完数”若因子之和大于该数，则称其为“盈数”*/int sum = FactorNum(i);if (sum == i) {wan.push_back(i);} else if (sum > i) {yin.push_back(i);}}printf("E:");//打印所有的完数 E: e1 e2 e3 .......(ei为完数)for (int i = 0; i < wan.size(); i++) {printf(" %d", wan[i]);}printf("\nG:");//打印所有的盈数G: g1 g2 g3 ......(gi为盈数)for (int i = 0; i < yin.size(); i++) {printf(" %d", yin[i]);}printf("\n");return 0;
}
​
​
代码分析

代码分析

对于以上的代码，我们要注意以下问题：

题目要求打印的格式是：E: e1 e2 e3 ......(ei为完数) G: g1 g2 g3 ......(gi为盈数) 其中两个数之间要有空格，行尾不加空格。所以我设置的思路是：

printf("E:"); 不加空格

printf(" %d", wan[i]); 遍历的时候空格加在前面

printf("\nG:"); E.G之间要换行；

结果吐槽：

一直自测不过，一提交竟然通过了；

剩下的树

题目：

剩下的树_牛客题霸_牛客网

输入：

500 3
100 200
150 300
470 471

输出：

298

分析：

500表示区间马路长度为500，3表示3个要移除树的区间，

然后再输入这3个区间；

最终输出就是剩下的树是多少。

输入：

L表示区间长度 M表示区间个数

再输入M个区间（left,right)

输出：移走所有区间的树之后剩下的树的个数 resultNum

思路：

创建一个数组vector<int> road(L+1);表示这条马路上有L颗树

我们可以将树存在设为0，树不存在设为1；

移走m棵树就等于将road数组中的m个0改为1；

最后看一下剩下有多少个0；

​
​

点评：这道题只要你理解了题目的输入，输出的含义；在代码实现上就不难了。故重在看懂题目；

结果：

糖果分享游戏

题目：

3426. 糖果分享游戏 - AcWing题库

一些学生围坐一圈，中间站着他们的老师，所有人都面向老师。 他们要玩一个有关糖果分享的游戏。 每个学生最开始都有一定数量的糖果（保证一定是偶数）。 每轮游戏的进程为： 老师吹起哨声，所有学生同时拿出自己一半数量的糖果，递给右边相邻的同学。 传递完成后，所有拥有奇数数量糖果的同学都将再得到一颗糖果。 游戏将不断进行，直到所有学生拥有的糖果数量均相等为止。 现在，给定所有学生的初始糖果数量，请确定游戏进行的总轮次数以及游戏结束后每个学生的糖果数量。 

分析：

1.输入：

第一行：N，表示学生数量

接下来N行：

输出： 以逆时针方向描述每个学生的初始糖果数量

2.输出：

首先输出游戏总轮次，然后输出游戏结束后每个人的糖果数量。

15 14
17 22
4 8

思路：

定义一个数组vector<int> canddys(N); (存储学生的糖果),并根据输入为它赋值。

处理游戏过程：

老师吹起哨声，所有学生同时拿出自己一半数量的糖果，递给右边相邻的同学。 传递完成后，所有拥有奇数数量糖果的同学都将再得到一颗糖果。

在每一轮循环中: 先把每个数的初值的一半存在一个数组OldNum中，把这些值赋给candy数组下一个数；

最后检查一下candy数组中的元素，若为奇数，则+1

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<vector>
using namespace std;
bool checkCandy(vector<int>& candy);
void swap(vector<int>& candy);
​
bool checkCandy(vector<int>& candy) {int resultNum = candy[0];for (int i = 1; i < candy.size(); i++) {if (candy[i] != resultNum) {return false;}}return true;
}
​
//实现交换糖果的数量
void swap(vector<int>& candy) {int size = candy.size();vector<int>oldNum(size);for (int i = 0; i < candy.size(); i++) {oldNum[i] = candy[i] / 2;}//再把oldNum中的值赋给candyNUm中的各位中的下一位for (int i = 0; i < size; i++) {candy[i] -= oldNum[i];candy[(i + 1)%size] += oldNum[i];
​}//再检查一遍candy数组，若有奇数值，则加1for (int i = 0; i < size; i++) {if (candy[i] % 2 == 1) {candy[i] ++;}}
}
​
​
int main() {int N;while (scanf("%d", &N)!= EOF) {if (N == 0) {break;}
​vector<int> candy(N);
​//为candy数组赋值for (int i = 0; i <N; i++) {scanf("%d", &candy[i]);}//循环的次数；int count = 0;//循环结束的标志：所有学生的糖果树相等while (checkCandy(candy) == false) {//交换糖果swap(candy);count++;}
​//最后输出总轮数和每个人的剩下的糖果的数量printf("%d %d\n", count,candy[0]);}return 0;
}
​

代码分析：

1.将动态数组作为某个函数的参数时，我们可以使用值传递也可以使用引用

为了节约脑细胞，我们在所有情况下都使用引用。

2.为了实现循环的效果，在把oldNum中的值赋给candyNUm中的各位中的下一位这个逻辑中，我们使用以下的逻辑：

其中注意candy[i]要先减掉oldNum[i]；且要用 candy[(i + 1)%size]加上oldNum[i];

 for (int i = 0; i < size; i++) {candy[i] -= oldNum[i];candy[(i + 1)%size] += oldNum[i];}