统计成绩问题
题目描述
读入N名学生的成绩，计算获得某一给定分数的学生人数。
输入描述
测试输入包含若干测试用例，每个测试用例的格式为
第1行：N 第2行：N名学生的成绩，相邻两数字用一个空格间隔。 第3行：给定分数
当读到N=0时输入结束。其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。
输出描述
对每个测试用例，将获得给定分数的学生人数输出。
样例输入：
4
70 80 90 100
80
3
65 75 85
55
5
60 90 90 90 85
90
0
思路与方法：
使用<vector>储存，再遍历找次数，没什么难度。
#include <iostream>
#include <vector>
#include <algorithm> // 建议包含此头文件以使用 count 函数
using namespace std;
int main()
{
int N;
int data;
int search;
// 循环读取N，当N为0时或输入无效时结束
while (cin >> N && N != 0)
{
vector<int> warehouse;
// 根据N的值读取相应数量的整数
for (int i = 0; i < N; i++)
{
cin >> data;
warehouse.push_back(data);
}
cin >> search; // 读取要查找的数字
int times = 0;
// 遍历vector，统计出现次数
for (auto num : warehouse)
{
if (num == search)
{
times++;
}
}
cout << times << endl;
}
return 0;
}
奇偶排序问题
题目描述
输入10个整数，彼此以空格分隔。重新排序以后输出(也按空格分隔)，要求: 1.先输出其中的奇数,并按从大到小排列； 2.然后输出其中的偶数,并按从小到大排列。
输入描述
任意排序的10个整数（0～100），彼此以空格分隔。
输出描述
可能有多组测试数据，对于每组数据，按照要求排序后输出，由空格分隔。
多组数据，注意输出格式
- 测试数据可能有很多组，请使用while(cin»a[0]»a[1]»…»a[9])类似的做法来实现;
- 输入数据随机，有可能相等。
实现思路：
读取数 -> 排序 -> 输出 -> 循环 一样难度不大。
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // 包含 std::greater
using namespace std;
// 为了代码整洁，将核心逻辑封装在 solve 函数中
void solve() {
vector<int> odds;
vector<int> evens;
int input_num;
// 循环读取10个整数
for (int i = 0; i < 10; ++i) {
cin >> input_num;
if (input_num % 2 != 0) { // 判断是否为奇数
odds.push_back(input_num);
} else { // 否则为偶数
evens.push_back(input_num);
}
}
// 1. 对奇数向量进行降序排序
sort(odds.begin(), odds.end(), greater<int>());
// 2. 对偶数向量进行升序排序
sort(evens.begin(), evens.end());
// 标志位，用于控制空格的输出
bool is_first_output = true;
// 3. 先输出所有奇数
for (int num : odds) {
if (!is_first_output) {
cout << " ";
}
std::cout << num;
is_first_output = false;
}
// 4. 再输出所有偶数
for (int num : evens) {
if (!is_first_output) {
cout << " ";
}
std::cout << num;
is_first_output = false;
}
// 输出换行符，为下一组输出做准备
scout << endl;
}
int main() {
// 设置cin, cout不与C风格的stdio同步，可以加速IO
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// 使用 peek() 检查输入流是否结束，这是处理多组数据的一种非常稳妥的方式
// 它会预读下一个字符但不会从流中移除它
while (cin.peek() != EOF && cin.peek() != '\n') {
solve();
}
return 0;
}
回文数问题
给一个正整数N，请你找到比N大的最小的那个回文数P。每组输入一个正整数N，N不超过10000位，并且N不包含前导0。
思路：
- 取输入数的前半部分，再镜像以得到一个结构上与
N最接近的回文数M。 - 将
M与N比较，如果M比N大，那么这个数就是我们要找的回文数。 - 如果
M不大于N，那么从中间值开始算，向两边进位加1，并且要计算可能导致的结果。 - 个人觉得可以进行字符串和数字之间的转换较好的解决这个问题，但是考虑到
N会超过10000位，还是手动进行操作。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 禁用C++流与C标准I/O的同步，以提高速度
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string n;
// 题目描述包含多组测试数据，使用 while 循环读取直到输入结束 (EOF)
while (cin >> n) {
int len = n.length();
string p = n;
// 步骤一：构建初始候选回文数 P
// 将字符串 n 的前半部分镜像到后半部分
for (int i = 0; i < len / 2; ++i) {
p[len - 1 - i] = p[i];
}
// 步骤二：检查 P 是否大于 N
if (p > n) {
cout << p << endl;
continue; // 处理下一组测试数据
}
// 步骤三：如果 P <= N，从中心位置开始增加数值
// mid1 指向左半边的最右侧字符，mid2 指向右半边的最左侧字符
// 如果长度为奇数，mid1 和 mid2 指向同一个中心字符
int mid1 = (len - 1) / 2;
int mid2 = len / 2;
// 从中心开始向外处理加法和进位
while (mid1 >= 0) {
if (p[mid1] == '9') {
// 如果是 '9'，变为 '0'，并继续向外进位
p[mid1] = '0';
p[mid2] = '0';
mid1--;
mid2++;
} else {
// 如果不是 '9'，直接加 1
p[mid1]++;
// 如果长度是偶数，中心有两个不同的字符，右边的也需要加1
if (mid1 != mid2) {
p[mid2]++;
}
// 加法完成，没有进位，可以退出循环
break;
}
}
// 步骤四：处理全 '9' 的特殊情况
// 如果 mid1 < 0，说明所有数字都是'9'，进位超出了字符串范围
// 例如：N = "99"，P 变为 "00"，mid1 变为 -1
if (mid1 < 0) {
cout << '1';
for (int i = 0; i < len - 1; ++i) {
cout << '0';
}
cout << '1' << endl;
} else {
// 输出常规情况下增加后的回文数 P
cout << p << endl;
}
}
return 0;
}
找零钱
纸币面额分为50 20 10 5 1 五种。请在知道要找多少钱n给小明的情况下，输出纸币数量最少的方案。1<=n<=99
Input
25
32
Output
20*1+5*1
20*1+10*1+1*2
很明显的贪心算法，比较好解决：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
// 提高 I/O 效率
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
// 循环处理多组输入数据，直到没有输入为止
while (cin >> n) {
// 定义纸币面额
int denominations[] = {50, 20, 10, 5, 1};
// 用一个 vector<string> 来存储结果的各个部分，方便最后用 '+' 连接
vector<string> result_parts;
// 遍历所有面额
for (int denom : denominations) {
// 计算当前面额需要的数量
int count = n / denom;
// 如果数量大于0，说明需要这种纸币
if (count > 0) {
// 将 "面值*数量" 的格式化字符串存入 vector
result_parts.push_back(to_string(denom) + "*" + to_string(count));
// 更新剩余需要找零的金额
n %= denom;
}
}
// 输出结果
for (int i = 0; i < result_parts.size(); ++i) {
cout << result_parts[i];
// 如果不是最后一个部分，就在后面加上 '+'
if (i < result_parts.size() - 1) {
cout << "+";
}
}
cout << endl;
}
return 0;
}
车厢调度
每辆火车从A驶入，再从B方向驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（n<=1000），分别按照顺序编号为1，2，3，…，n。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨，它就不能再回到车站C。求能否使它以a1,a2,…,an的顺序从B方向驶出。
思路：实际上是一个比较经典的栈问题
我们按顺序处理 1 到 n 号车厢。对于每一节进站的车厢，我们先让它进入中转站 C（入栈）。然后，我们立刻检查中转站 C 的出口（栈顶）的车厢是否是我们当前期望在出口 B 看到的下一节车厢。
- 如果是，就让它出站（出栈），然后继续检查新的栈顶车厢，直到栈顶的车厢不再是所期望的，或者中转站变空。
- 如果不是，我们就让下一节车厢从 A 进站。
所有车厢（1 到 n）都进站后，如果中转站 C 最终为空，说明所有车厢都按照指定的顺序成功出站了。如果中转站 C 中还有剩余的车厢，则说明无法形成指定的顺序。
代码实现：
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
// 提高 I/O 效率
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
// 题目中输入只有一组，但为了代码健壮性，使用 while 也能处理
while (cin >> n) {
// 存储指定的出站顺序
vector<int> target_order(n);
for (int i = 0; i < n; ++i) {
cin >> target_order[i];
}
// 模拟中转站C的栈
stack<int> station;
// 一个索引，用于指向 target_order 中下一个期望出站的车厢
int target_idx = 0;
// 模拟1到n号车厢依次从A入口进站
for (int incoming_car = 1; incoming_car <= n; ++incoming_car) {
// 车厢进入中转站C（入栈）
station.push(incoming_car);
// 只要中转站不空，并且栈顶的车厢是我们想要的，就让它出站
while (!station.empty() && station.top() == target_order[target_idx]) {
// 车厢出站（出栈）
station.pop();
// 期望的下一节车厢的索引后移
target_idx++;
}
}
// 所有车厢都处理完毕后，检查中转站是否为空
// 如果为空，说明所有车厢都按顺序出站了
if (station.empty()) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
八数码问题
初始状态的步数就算1， 输入：第一个3*3的矩阵是原始状态，第二个3*3的矩阵是目标状态。 输出：移动所用最少的步数
Input
2 8 3
1 6 4
7 0 5
1 2 3
8 0 4
7 6 5
Output
6
解决思路：
- 状态表示：将3x3的矩阵转换为字符串（如"283164705"），便于存储和比较。
- BFS初始化：从初始状态开始，步数为1（包括初始状态）。
- 状态扩展：对于每个状态，找到空格（0）的位置，尝试向四个方向（上、下、左、右）移动，生成新状态。
- 避免重复：使用哈希集合记录已访问的状态，避免重复处理。
- 目标检测：如果当前状态与目标状态相同，返回当前步数。
- 步数更新：每移动一次，步数增加1。
本题用到了对stack，queue，unordered_set的使用。
#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int dx[4] = {-1, 1, 0, 0}; // 上下左右
int dy[4] = {0, 0, -1, 1};
int bfs(string start, string target) {
if (start == target) return 1;
queue<pair<string, int>> q;
unordered_set<string> visited;
q.push({start, 1});
visited.insert(start);
while (!q.empty()) {
auto [state, steps] = q.front();
q.pop();
int pos = state.find('0');
int x = pos / 3, y = pos % 3;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
int new_pos = nx * 3 + ny;
string new_state = state;
swap(new_state[pos], new_state[new_pos]);
if (new_state == target)
return steps + 1;
if (visited.find(new_state) == visited.end()) {
visited.insert(new_state);
q.push({new_state, steps + 1});
}
}
}
}
return -1; // 无解（题目保证有解，此步不会执行）
}
int main() {
string start = "", target = "";
int num;
// 读取初始状态
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cin >> num;
start += ('0' + num);
}
}
// 读取目标状态
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cin >> num;
target += ('0' + num);
}
}
cout << bfs(start, target) << endl;
return 0;
}
当总统问题
小明想当H国的总统，H国大选是按各州的投票结果来确定最终的结果的，如果得到超过一半的州的支持就可以当选，而每个州的投票结果又是由该州选民投票产生的，如果某个州超过一半的选民支持小明，则他将赢得该州的支持。现在给出每个州的选民人数，请问小明至少需要赢得多少选民的支持才能当选？
输入包含多组测试数据。
每组数据的第一行是一个整数N（1<=N<=101）,表示H国的州数，当N=0时表示输入结束。
接下来一行包括N个正整数，分别表示每个州的选民数，每个州的选民数不超过100。
Input
3
5 7 5
0
Output
6
思路：比较明显的贪心算法，需要先将州选民排序，然后从一半再多一个处开始遍历，每个州的一半人再加一个人调出来再累加即可。
#include <iostream>
#include <vector>
#include <numeric> // std::accumulate
#include <algorithm> // std::sort
// 使用 std 命名空间
using namespace std;
int main() {
// 提高 I/O 效率
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
// 当 N=0 时表示输入结束
while (cin >> n && n != 0) {
// win_costs 向量用于存储赢得每个州的 "成本"
vector<int> win_costs;
for (int i = 0; i < n; ++i) {
int voters;
cin >> voters;
// 计算赢得该州所需的最少票数并存入
win_costs.push_back((voters / 2) + 1);
}
// 将赢得各州的成本从小到大排序
sort(win_costs.begin(), win_costs.end());
// 计算需要赢得的州数
int states_to_win = (n / 2) + 1;
int total_min_votes = 0;
// 累加前 states_to_win 个最低成本
int total_min_votes = accumulate(win_costs.begin(), win_costs.begin() + states_to_win, 0);
// 输出结果
cout << total_min_votes << endl;
}
return 0;
}
棋盘放置问题
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
输入含有多组测试数据。
每组数据的第一行是两个正整数n和k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。（n<=8，k<=n）
当n和k均为-1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（不可放棋子的区域，数据保证不出现多余的空白行或者空白列）。
对于每一组数据，给出一行输出，输出摆放的方案数目C（数据保证C<2^31）。
Input
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
Output
2
1
思路：
基本思路是使用DFS进行深度遍历，以行为标准搜索，列则可以通过另一个数组进行标记。在每一行可以选择放置，也可以选择跳过。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 全局变量，方便在递归函数中访问
int n, k;
vector<string> board; // 存储棋盘形状
vector<bool> col_used; // 标记列是否被占用
long long solution_count; // 存储方案总数
/**
* @brief 使用深度优先搜索（回溯）来查找解决方案
* @param row 当前正在处理的行号
* @param k_left 还需要摆放的棋子数量
*/
void dfs(int row, int k_left) {
// 成功找到一个解：所有棋子都已摆放完毕
if (k_left == 0) {
solution_count++;
return;
}
// 无法找到解：行数已经用完，但棋子还没放完
if (row >= n) {
return;
}
// --- 递归探索 ---
// 可能性一：在当前行 (row) 摆放一个棋子
for (int j = 0; j < n; ++j) {
// 检查位置是否有效 (是'#'且该列未被占用)
if (board[row][j] == '#' && !col_used[j]) {
// “选择”：占用该列
col_used[j] = true;
// “探索”：进入下一行，需要摆放的棋子数减一
dfs(row + 1, k_left - 1);
// “撤销选择”（回溯）：释放该列，以便其他分支的搜索可以使用
col_used[j] = false;
}
}
// 可能性二：不在当前行摆放棋子，直接进入下一行
// 这是一个剪枝：如果剩下的行数已经不够放剩下的棋子了，就没必要继续了
if (n - (row + 1) >= k_left) {
dfs(row + 1, k_left);
}
}
int main() {
// 提高cin/cout的效率
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// 循环读取输入，直到 n 和 k 均为 -1
while (cin >> n >> k && (n != -1 || k != -1)) {
// 读取棋盘
board.resize(n);
for (int i = 0; i < n; ++i) {
cin >> board[i];
}
// 重置状态
solution_count = 0;
col_used.assign(n, false);
// 从第0行开始搜索，需要摆放k个棋子
dfs(0, k);
// 输出结果
cout << solution_count << endl;
}
return 0;
}