29. 书籍叠放
题目描述
假设书本的叠放有这样的规则，当A书的长度和宽度都大于B书时，可以将其B书置于A的上方，堆叠摆放，请设计一个程序，根据输入的书本长宽，计算最多可以堆叠摆放多少本书？输入
[[16,15], [13, 12], [15, 14]]输出
3说明
这里代表有3本书，第1本长宽分别为16和15，第2本长宽为13和12，第3本长宽为15和14，它们可以按照[13, 12],[15, 14],[16,15]的顺序堆叠，所以输出3
一、问题分析
首先读题，仔细看描述中的内容，发现需求是
1.假设书本的叠放有规则：当A书的长度和宽度都大于B书时，可以将其B书置于A的上方，堆叠摆放，请设计一个程序，根据输入的书本长宽，计算最多可以堆叠摆放多少本书？
2.输入：[[16,15],[13,12],[15,14]]
3.输出：3
二、解题思路
1.首先我们接收数据，char str[1000];
scanf("%s",str);
2.我们通过遍历字符串，查找字符串中‘[’的数量减去1就是我们书本的数目，使用一个变量int num = 0;存储
3.然后我们定义一个数组用来存放书本的长度和宽度，
int book[num][2];
4.将长度和宽度读取到book中
int idx = 2;
for(int i = 0; i < num; i++) {
if(str[idx] != '\0' && !isdigit(str[idx])) idx++;
int tempnum = str[idx++];
while(isdigit(str[idx])) {
tempnum = tempnum * 10 + str[idx++];
}
book[i][0] = tempnum;
if(str[idx] == ',') {
tempnum = str[++idx];
while(isdigit(str[idx])) {
tempnum = tempnum * 10 + str[idx++];
}
book[i][1] = tempnum;
}
}
5.我们对book进行排序，长和宽都小的放在前面
qsort(book, num, sizeof(book[0]), compare);
6.比较函数
int compare(const void* a, const void* b) {
int (*arr_a)[2] = (int (*)[2])a;
int (*arr_b)[2] = (int (*)[2])b;
return ((*arr_a)[0] < (*arr_b)[0]) && ((*arr_a)[1] < (*arr_b)[1]);
}
7.然后还需要遍历数组，如果遇到后面的书的长度或者宽度比前面的书短的情况我们停止
if(num == 1) {
printf("1\n");
return 0;
}
int count = 1;
for(int i = 1; i < num, i++) {
if(book[i][0] < book[i - 1][0] || book[i][1] < book[i - 1][1]) {
break;
}
count++;
}
8.最后输出结果就可以了
printf("%d\n", count);
三、具体步骤
使用的语言是C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
int compare(const void* a, const void* b) {
int (*arr_a)[2] = (int (*)[2])a;
int (*arr_b)[2] = (int (*)[2])b;
return (*arr_a)[1] > (*arr_b)[1] && (*arr_a)[0] > (*arr_b)[1];
}
int main() {
char str[1000];
fgets(str, sizeof(str), stdin);
str[strcspn(str, "\n")] = '\0';
// printf("输入：%s\n", str);
// 计算书本数量
int num = 0;
for (int i = 0; str[i] != '\0'; i++) {
if (str[i] == '[') {
num++;
// printf("一共%d本书\n", num);
}
}
num--; // 减去外层的大括号对应的数量
// printf("一共%d本书\n", num);
// 动态分配内存用于存储书本长和宽信息
int book[num][2];
// 使用sscanf函数解析字符串，提取书本长和宽信息并存入book数组
int idx = 1;
for (int i = 0; i < num; i++) {
idx++; // 跳过'['
sscanf(str + idx, "%d,%d", &book[i][0], &book[i][1]);
// 找到下一个'['的位置，更新idx
// printf("第%d本书本的长%d宽%d\n", i, book[i][0], book[i][1]);
while (str[idx] != '\0' && str[idx] != '[') {
idx++;
}
}
// 对书本数组进行排序
qsort(book, num, 2 * sizeof(int), compare);
// for (int i = 0; i < num; i++) {
// printf("第%d本书的长度%d宽度%d\n", i, book[i][0], book[i][1]);
// }
// 判断可堆叠书本数量
int count = 1;
if (num == 1) {
printf("1\n");
} else {
for (int i = 1; i < num; i++) {
if (book[i][0] < book[i - 1][0] || book[i][1] < book[i - 1][1]) {
break;
}
count++;
}
printf("%d\n", count);
}
return 0;
}