目录
序列排序
【题目描述】
对于给定的正整数序列,按照每个数的各位数和从大到小排序,各位数和相同的按照本身大小排序,大的在前,小的在后。
【输入格式】
第一行1个整数n,表示序列的大小。( 0 < n ≤ 1000) 第二行n个正整数,表示序列的每个数,每个数不大于100000000。
【输出格式】
输出按照题目要求排序后的序列
【输入样例】
6
17 26 9 13 88 10
【输出样例】
88 9 26 17 13 10
一、分析题目
- 首先需要编写一个函数来计算一个整数的各位数字之和。
- 然后使用排序算法(如
sort
函数)对给定的整数序列进行排序,排序的比较规则是先比较各位数字之和,如果各位数字之和相同,再比较数字本身的大小。
二、解题步骤
- 定义一个函数
digitSum
用于计算一个整数的各位数字之和。 - 定义比较函数
compare
,用于sort
函数排序时的比较规则。 - 在
main
函数中读取输入的整数序列,调用sort
函数进行排序,最后输出排序后的序列。
三、代码实现
#include <bits/stdc++.h>
using namespace std;
// 计算一个整数的各位数字之和的函数
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
// 比较函数,用于排序
bool compare(int a, int b) {
int sumA = digitSum(a);
int sumB = digitSum(b);
// 首先按照各位数字之和从大到小排序
if (sumA!= sumB) {
return sumA > sumB;
}
// 如果各位数字之和相同,按照数字本身从大到小排序
return a > b;
}
int main() {
int n;
cin >> n;
vector<int> numbers;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
numbers.push_back(num);//添加到末尾
}
// 使用自定义的比较函数对序列进行排序
sort(numbers.begin(), numbers.end(), compare);
for (int i = 0; i < numbers.size(); ++i) {
cout << numbers[i] << " ";
}
return 0;
}
也可以使用动态分配的数组 numbers
来存储输入的数字序列,排序完成后输出序列,并在最后释放了动态分配的内存
#include <iostream>
using namespace std;
// 计算一个整数的各位数字之和的函数
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
// 比较函数,用于排序
bool compare(int a, int b) {
int sumA = digitSum(a);
int sumB = digitSum(b);
// 首先按照各位数字之和从大到小排序
if (sumA!= sumB) {
return sumA > sumB;
}
// 如果各位数字之和相同,按照数字本身从大到小排序
return a > b;
}
int main() {
int n;
cin >> n;
int *numbers = new int[n]; // 动态分配内存来存储数字序列
for (int i = 0; i < n; i++) {
cin >> numbers[i];
}
// 使用冒泡排序算法进行排序
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (!compare(numbers[j], numbers[j + 1])) {
int temp = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;
}
}
}
for (int i = 0; i < n; i++) {
cout << numbers[i] << " ";
}
delete[] numbers; // 释放动态分配的内存
return 0;
}
还可以使用其他排序算法来替代这段冒泡排序的代码,以下是使用插入排序的示例:
#include <bits/stdc++.h>
using namespace std;
// 计算一个整数的各位数字之和的函数
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
// 比较函数,用于排序
bool compare(int a, int b) {
int sumA = digitSum(a);
int sumB = digitSum(b);
// 首先按照各位数字之和从大到小排序
if (sumA!= sumB) {
return sumA > sumB;
}
// 如果各位数字之和相同,按照数字本身从大到小排序
return a > b;
}
int main() {
int n;
cin >> n;
int *numbers = new int[n]; // 动态分配内存来存储数字序列
for (int i = 0; i < n; i++) {
cin >> numbers[i];
}
// 使用插入排序算法进行排序
for (int i = 1; i < n; i++) {
int key = numbers[i];
int j = i - 1;
while (j >= 0 &&!compare(numbers[j], key)) {
numbers[j + 1] = numbers[j];
j = j - 1;
}
numbers[j + 1] = key;
}
for (int i = 0; i < n; i++) {
cout << numbers[i] << " ";
}
delete[] numbers; // 释放动态分配的内存
return 0;
}
还可以使用快速排序、归并排序等排序算法,以下是快速排序的示例:
#include <iostream>
using namespace std;
// 计算一个整数的各位数字之和的函数
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
// 比较函数,用于排序
bool compare(int a, int b) {
int sumA = digitSum(a);
int sumB = digitSum(b);
// 首先按照各位数字之和从大到小排序
if (sumA!= sumB) {
return sumA > sumB;
}
// 如果各位数字之和相同,按照数字本身从大到小排序
return a > b;
}
// 交换两个元素
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 对数组进行划分
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (compare(arr[j], pivot)) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// 快速排序函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int n;
cin >> n;
int *numbers = new int[n]; // 动态分配内存来存储数字序列
for (int i = 0; i < n; i++) {
cin >> numbers[i];
}
// 使用快速排序算法进行排序
quickSort(numbers, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << numbers[i] << " ";
}
delete[] numbers; // 释放动态分配的内存
return 0;
}
【题目描述】
任给两个正整数N、M,求一个最小的正整数a,使得a和(M-a)都是N的因子。
【输入格式】
包括两个整数N、M。N不超过1,000,000。
【输出格式】
输出一个整数a,表示结果。如果某个案例中满足条件的正整数不存在,则在对应行输出-1
【样例输入】
35 10
【样例输出】
5
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
int f=0;
for(int a=1; a<=n; a++) {
if(n%a==0&&n%(m-a)==0) {
f=a;
break;
}
}
if(f) {
cout<<f;
} else {
cout<<-1;
}
return 0;
}
图像模糊处理
描述:给定n行m列的图像各像素点的灰度值,要求用如下方法对其进行模糊化处理:
- 四周最外侧的像素点灰度值不变;
2.中间各像素点新灰度值为该像素点及其上下左右相邻四个像素点原灰度值的平均(舍入到最接近的整数)。
输入描述
第一行包含两个整数n和m,表示图像包含像素点的行数和列数。1<=n<=100,。接下来n行,每行m个整数,表示图像的每个像素点灰度。相邻两个整数之间用单个空格限开,每个元素均在0-255之间。
输出描述
m行,每行n个整数,为模糊处理后的图像。相邻两个整数之间用单个空格隔开
用例输入
4 5
100 0 100 0 50
50 100 200 0 0
50 50 100 100 200
100 100 50 50 100
输出
1000100050
5080100600
508010090200
1001005050100
一、整体思路
- 首先,我们从用户那里获取图像的行数n和列数m,以及每个像素点的灰度值,并将这些灰度值存储在二维整数数组a中。
- 接下来,我们分两部分处理这些像素点。对于图像四周最外侧的像素点(即第一行、最后一行、第一列和最后一列的像素点),直接将它们的灰度值原封不动地复制到二维双精度数组b中。
- 对于处于图像内部(除了四周最外侧)的像素点,我们计算它们新的灰度值。新灰度值是该像素点及其上下左右相邻四个像素点原灰度值的平均值,并使用round函数将结果四舍五入到最接近的整数,然后将这个结果存储在数组b的对应位置。
- 最后,我们将处理后的像素灰度值逐行输出。
二、代码步骤分析
(一)输入数据
- 定义两个整型变量n和m来分别存储图像的行数和列数。
- 使用cin从标准输入读取n和m的值,确定图像的大小。
(二)初始化和处理边界像素
- 定义二维数组a来存储输入的原始像素灰度值,二维数组b用于存储处理后的像素灰度值。
- 使用两个嵌套的for循环遍历输入的像素灰度值,并将其存储到数组a中。
- 在同一个嵌套循环中,判断当前像素是否处于图像的边界(第一行、最后一行、第一列、最后一列)。如果是边界像素,直接将其灰度值复制到b数组的对应位置。
(三)处理内部像素
- 使用另外一组嵌套的for循环,遍历图像内部的像素(即除了边界像素之外的像素)。
- 对于每个内部像素,计算它及其上下左右相邻四个像素的灰度值的平均值,并将结果存储到b数组的对应位置。
(四)输出结果
- 使用两个嵌套的for循环,将处理后的b数组中的像素灰度值逐行输出到标准输出。
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
// 主函数
int main() {
int a[N][N]; // 定义整数二维数组 a,用于存储原始像素点灰度值
double b[N][N]; // 定义双精度浮点数二维数组 b,用于存储模糊处理后的像素点灰度值
int n = 0, m = 0;
cin >> n >> m; // 输入像素点的行数 n 和列数 m
for (int i = 0; i < n; i++) { // 外层循环,遍历每一行
for (int j = 0; j < m; j++) { // 内层循环,遍历每一行中的每一列
cin >> a[i][j]; // 输入每个像素点的灰度值
if (i == n - 1 || i == 0 || j == 0 || j == m - 1) {
// 如果是四周最外侧的像素点
b[i][j] = a[i][j];
// 直接将原始灰度值赋值给处理后的数组对应位置
}
}
}
for (int i = 1; i < n - 1; i++) { // 遍历除了第一行和最后一行的中间行
for (int j = 1; j < m - 1; j++) { // 遍历除了第一列和最后一列的中间列
// 计算中间像素点新灰度值为该像素点及其上下左右相邻四个像素点原灰度值的平均
b[i][j] = (a[i][j] + a[i - 1][j] + a[i + 1][j] + a[i][j - 1] + a[i][j + 1]) / 5.0;
}
}
for (int i = 0; i < n; i++) { // 输出模糊处理后的图像
for (int j = 0; j < m; j++) {
cout << round(b[i][j]) << "";
// 对处理后的灰度值进行四舍五入,并输出
}
cout << endl;
}
return 0;
}
吉利号码
【题目描述】
中国人喜欢图吉利,包括吉利数字,例如数字 8 或者数字 6,尤其是连着的数字更加喜欢,比如手机号码,汽车车牌,房间号码等等。有需求就会有市场,吉利数字的号码,往往意味着更贵的价格。请你根据以下规则,编写一个程序,根据规则给一个号码设置相应的价格。
具体规则如下:
正常号码是 100 元。含有:6,8 任何一个数字,每出现一次加分。50 元,例如 4326,6875,9918都符合加分标准。其中,6875 被加 2 个 50 元,就相当于加 100 元;9918 被加 50 元。如果出现升序或者降序的情况,不管升序还是降序,号码涨价 3 倍。例如:5678,4321 都要贵 3 倍。注意:例如 5567,4331 等有相同元素的号码不算降序、升序。
如果出现三个相同数字情况,都涨 6 倍。例如:4888,6665,7777 都满足加分
的标准。注意:7777 因为满足这条标准两次,所以这条规则给它涨两个 6
倍,也就是 12 倍。
如果符合 AABB 或者 ABAB 模式的,价格涨一倍。例如:2255,3939,7777 都符
合这个模式,所以都会涨价。注意:7777 因为满足这条标准两次,所以这条
标准给它涨 2 倍,同时 7777 也是连号,也会在之前连号的基础上继续涨价。
请编写程序按照所有规则,求一个号码的最终价格!要求程序从标准输入接收数
据,在标准输出上输出结果。
【输入格式】
输入共 1 行,输入一个四位正整数,就是待计算的号码。
【输出格式】
输出共 1 行,一个整数,表示这个号码对应的销售价格。
【样例输入】(测试数据不包含本样例)
6543
【样例输出】
450
解题思路:采用分步处理的方式,遍历每一位数字并应用相应的规则来更新价格。以下是一个简单的解题思路:
- 定义一个函数 int calculatePrice(int number),接受一个四位整数作为参数。
- 初始化价格变量 price = 100,代表默认的基础价格。
- 使用循环,对于每一位数字(从右到左),检查是否满足特定条件:
- 如果是 6 或 8,将价格加上 50。
- 如果连续出现两个相同的数字(如 66 或 88),增加 6 倍(先判断是否有三连同再判断二连同)。
- 如果数字是 6 或 8 的序列(如 666 或 888),分别算作一个 50 元加分,然后额外加上两倍的 6 倍。
- 对于 AABB 和 ABAB 格式,价格翻倍,注意如果满足多次,只计算一次加倍。
- 检查当前数字与其前一位(如有)是否构成升序或降序,如果是,则价格乘以 3。
- 返回计算后的价格。
#include <iostream> using namespace std; int calculatePrice(int number) { int price = 100; // 初始价格为 100 元 // 检查数字 6 或 8 的出现次数 int numCopy = number; while (numCopy > 0) { int digit = numCopy % 10; if (digit == 6 || digit == 8) { price += 50; } numCopy /= 10; } // 检查升序或降序 int digit1 = number / 1000; int digit2 = (number % 1000) / 100; int digit3 = (number % 100) / 10; int digit4 = number % 10; bool isAscending = (digit1 < digit2 && digit2 < digit3 && digit3 < digit4); bool isDescending = (digit1 > digit2 && digit2 > digit3 && digit3 > digit4); if (isAscending || isDescending) { price *= 3; } // 检查三个相同数字 numCopy = number; int digitCount[10] = {0}; while (numCopy > 0) { digitCount[numCopy % 10]++; numCopy /= 10; } for (int i = 0; i < 10; i++) { if (digitCount[i] >= 3) { price *= 6; } } // 检查 AABB 或 ABAB 模式 numCopy = number; int digit1_ = numCopy % 10; numCopy /= 10; int digit2_ = numCopy % 10; numCopy /= 10; int digit3_ = numCopy % 10; numCopy /= 10; int digit4_ = numCopy % 10; if ((digit1_ == digit2_ && digit3_ == digit4_) || (digit1_ == digit3_ && digit2_ == digit4_)) { price *= 2; } return price; } int main() { int inputNumber; cin >> inputNumber; int finalPrice = calculatePrice(inputNumber); cout << finalPrice <<endl; return 0; }
战胜白蚁
【题目描述】
小明因为很长时间没有回家,发现他家被白蚁给入侵了,白蚁特别喜欢啃食木头,
因此他家的地板就遭殃了。小明要抢救被白蚁破坏的木地板,每个木地板由于白蚁的数量不同,每个地板进行维修的时间也不同,同时要争取及时修理越好,否则超过某个时间,这块地板就会被严重破坏掉。小明只能一块一块的清理白蚁,不能并行操作,也就是不能同时修多块地板。请编写一个程序,根据每个地板的修理时间和如果不修理就会被白蚁完全损毁的时间,进行一个最合理的排序,使得可以抢救最多的木板。输入是木板的数目,以及每个木板的维修时间和被破坏的时间,输出是能抢救的最多木板的数量。
【输入格式】
第一行是一个整数 N(N 小于 50000),接下来 N 行每行两个整数 T1,T2描述一个要修理的木板:修理这个木板需要 T1秒,如果在 T2秒之内还没有修理完成,这个木板就报废了。
【输出格式】
输出一个整数 S,表示最多可以抢修 S 个木板。
【样例输入】(测试数据不包含本样例)
4
100 200
200 1300
1000 1250
2000 3200
【样例输出】
3
代码定义了一个名为 Board 的结构体,其中有两个整数字段:repairTime 和 destroyTime 分别代表修复每块地板所需的时间和如果没有及时修复会被破坏的时间。
函数 compare 定义了一个比较函数,用于对地板数组按照损坏时间减去修复时间的差值进行升序排序,这样优先处理那些修理时间较短、需要尽快修复的地板。
rescueBoards 函数接收一个整数 N 表示地板数量,并读取所有地板的修理时间和破坏时间。然后使用 sort 函数根据之前定义的比较函数对地板数组进行排序。接着遍历排序后的数组,逐块修复地板,计算总共能抢救的最大地板数。只有当修复当前地板所需时间不超过剩余的破坏时间时,才计入抢救计数。
main 函数从用户那里获取地板数量 N,调用 rescueBoards 函数得到结果,最后输出能抢救的地板数。
#include <bits/stdc++.h>
using namespace std;
// 定义结构体 Board,用于存储每个木板的维修时间和破坏时间
struct Board {
int repairTime; // 维修一块木板所需的时间
int destroyTime; // 若未在该时间内维修好,木板会损坏的时间
};
// 比较函数,用于对木板按照破坏时间减去维修时间的差值进行比较
bool compare(Board a, Board b) {
return a.destroyTime - a.repairTime < b.destroyTime - b.repairTime;
}
// 救援木板的函数,输入木板数量 N
int rescueBoards(int N) {
Board boards[N]; // 创建一个大小为 N 的 Board 类型数组,用于存储木板信息
// 循环读取每块木板的维修时间和破坏时间
for (int i = 0; i < N; i++) {
cin >> boards[i].repairTime >> boards[i].destroyTime;
}
// 对木板数组按照比较函数进行排序
sort(boards, boards + N, compare);
int time = 0; // 记录已花费的维修总时间
int count = 0; // 记录成功抢救的木板数量
// 遍历排序后的木板数组
for (int i = 0; i < N; i++) {
time += boards[i].repairTime; // 累加当前木板的维修时间
// 如果累加后的维修总时间小于等于当前木板的破坏时间
if (time <= boards[i].destroyTime) {
count++; // 抢救成功数量加 1
} else { // 否则,无法在规定时间内维修这块木板
break; // 停止后续计算
}
}
return count; // 返回抢救成功的木板数量
}
// 主函数
int main() {
int N; // 存储输入的木板数量
cin >> N; // 读取木板数量
int result = rescueBoards(N); // 调用救援木板函数并获取结果
cout << result << endl; // 输出抢救成功的木板数量
return 0;
}