✨题目链接：
MT8 奇数位丢弃
✨题目描述
对于一个由 0..n 的所有数按升序组成的序列，我们要进行一些筛选，每次我们丢弃去当前所有数字中第奇数位个的数。重复这一过程直到最后剩下一个数。请求出最后剩下的数字。
数据范围： 1≤𝑛≤1000 1≤n≤1000 ，本题有多组输入
✨输入描述:
每组数据一行一个数字，为题目中的n(n小于等于1000)。
✨输出描述:
一行输出最后剩下的数字。
✨示例1
📍输入
500
📍输出
255
✨解题思路
先从题目中提炼关键词：
- 数按升序组成的序列 由 0 到 n组成
- 每次去掉奇数位
- 本题有多组输入
思路：
- 逆行思考，每次留下偶数位
- 把0到n的数放到vector中，我们叫v1
- 从v1中取偶数位 放到 vector v2 中
- 循环n次，因为最多都不会超过n次，我们只需要中间跳出循环就可以
- 因为 移动 奇数次是从 v1->v2 的 移动偶数次 是从 v2->v1 的，所以每次的移动都要判断移动次数的奇偶
- 每一次移动完成后需要判断，被更新的vector 的 size 是否为 1 如果为 1 说明只剩下了一个数字，此时这个数字就是结果
- 更新前清理v1或者v2
✨代码
#include <iostream>
#include <vector>
using namespace std;int main() {vector<int> v1, v2;int num;while (cin >> num) {v1.clear();v2.clear();char ch = getchar();if (ch == '\n') {for (int i = 0; i <= num; i++) {v1.push_back(i);}for (int i = 1; i <= num; i++) {if (i % 2 != 0) {v2.clear();for (int j = 1; j < v1.size(); j++) {if (j % 2 != 0) {v2.push_back(v1[j]);}}if (v2.size() == 1) {cout << v2[0] << endl;break;}} else {v1.clear();for (int j = 1; j < v2.size(); j++) {if (j % 2 != 0) {v1.push_back(v2[j]);}}if (v1.size() == 1) {cout << v1[0] << endl;break;}}}}}return 0;
}
※ 如果文章对你有帮助的话，可以点赞收藏！！谢谢支持
