B1023. 组个最小数
(4.4 贪心)
思路:
- 先在1~9这9个数字中,确定最高位,0不能作最高位。但是确定完最高位的数字后要及时中断循环。因为除最高位以外的数字,是可以用0的。
- 因为所有数字都必须参与组合,所以最后结果的位数是确定的。
- 确定完最高位后,剩下的所有位,也是从高位到低位优先选择[0, 9]中还存在的最小的数输出。
写代码碰到的问题:
- 最高位找到一个后,就break。假设最高位是1,就算后面还有100个1,输出一个1后也要break,将后面的100个1带到后面的循环中,和0一起从高到低输出。
- 最后输出的时候,是双重嵌套循环,外层是0~9每个数字的遍历,内层则是当前数字的count[i]数量。数字i有多少个,就输出多少个。
完整代码:
#include <cstdio>
int main()
{
// 记录数字0~9的个数
int count[10];
for (int i = 0; i < 10; i++)
{
scanf("%d", &count[i]);
}
// 从1~9中选择count不为0的最小的数字
// 确定最高位
for (int i = 1; i < 10; i++)
{
if (count[i] > 0)
{
printf("%d", i);
count[i]--;
// 找到一个之后就break
// 0之后最小的是1,如果有两个1,也是确定一个1以后就要break
// 因为这个时候最高位已经确定了,就算还有1,也要加上0了
break;
}
}
// 从0~9输出对应个数的数字
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < count[i]; j++)
{
printf("%d", i);
}
}
return 0;
}
B1024. 科学计数法
(3.6 字符串处理)
思路:
- 科学计数法是满足正则表达式的,也就是说数字的整数部分只有1位,小数部分至少有1位,最后的正负号即使对正数,也会明确给出(指的是科学计数法)。
- 首先要定除字母E的位置pos,然后要计算出指数的大小exp,整体分为两种情况——指数为正和指数为负。
- 指数为负——先要printf出0.000····,至于有多少个0,有(exp - 1)个0。
下面将输出整数部分str[1],然后从str[3]开始输出数字。因为str[2]是小数点。
注意:str[]字符串一直是不变的,只不过是用不同的格式将str[]的各个部分输出罢了。- 指数为正——首先将输出范围限定在[1, pos)区间。碰到小数点略过就好。当下标i到达(exp+2)的位置时候,说明这个时候小数点移动的位数已经够了。同时,原小数点后的数字个数如果等于exp,说明这种情况,小数点恰好在输出后新的数字的最右边,是不需要输出小数点的。
这时,要注意一种情况,就是(pos - 3)和exp的大小问题。
(pos-3)比exp大,就要输出小数点,因为右移位数没有要输出的数字多
(pos-3)比exp小于等于,就不用输出小数点,因为输出的数字很少,右移位数大,后面要补0。
补0的个数就是exp - (pos - 3)个0。
- 记住代码首先要应付特殊情况,这里的就是指数为0就是特殊情况。
完整代码中有详细的注释——
#include <cstdio>
#include <cstring>
int main()
{
char str[10010];
gets_s(str);
int len = strlen(str);
// 如果是负数,输出负号
if (str[0] == '-') printf("-");
// pos用来存放字符串中E的位置
int pos = 0;
// 使用pos来不断寻找E的位置
// pos找到E以后,直接退出,不再pos++
while (str[pos] != 'E')
{
pos++;
}
// exp用来存放指数(先不考虑正负)
int exp = 0;
// 为什么是pos+2呢?因为就是Pos本身加上后面的正负号,一共2位,所以pos+2刚好下标到正负号后面的第一位数字
for (int i = pos + 2; i < len; i++)
{
exp = exp * 10 + (str[i] - '0');
}
// 特殊情况
// 特判指数为0的情况
if (exp == 0)
{
// pos表示指数E的位置,因为E为0,所以指数本身及其后面的不用考虑了,输出指数前的部分即可
for (int i = 1; i < pos; i++)
{
// i=1的原因是,正数的话就忽略+号,不用管,直接从第一位数字开始输出
// 负数的话,一开始已经输出-号了,所以也不用管,还是从-号后的第一位数字开始输出
printf("%c", str[i]);
}
}
// 如果指数为负
if (str[pos + 1] == '-')
{
// 因为无论输入的这个整数是正的还是负的
// 整数部分只有一位,所以如果指数为负,就算是-1,也是0.XXX这种形式
printf("0.");
// 输出(exp - 1)个0
// 如果指数是负的,还是-1,那么就不用多输出0了
// 但如果不是,可以采用这个方法——再输出(exp - 1)个0
for (int i = 0; i < exp - 1; i++)
{
printf("0");
}
// 输出除了小数点以外的数字
// 就是原先输入的整数,小数点左右两边的数字要进行输出
// 首先输出整数部分,整数部分只有1位,也就是str[1]
// 因为小数点也算一个字符,它是str[2],所以小数点右边的第一个数字的下标是str[3]
printf("%c", str[1]);
for (int i = 3; i < pos; i++)
{
// 就算E前面有几个0,也要输出,因为0也是有效位
// 所以终点是pos,也就是E的位置之前的数字全部输出
printf("%c", str[i]);
}
}
// 如果指数为正
else
{
// 输出小数点移动之后的数
// 0也要同时输出,毕竟也是有效位
for (int i = 1; i < pos; i++)
{
// 输出只有一位的整数后,如果碰到了小数点,就略过原小数点
if (str[i] == '.') continue;
// 输出当前数位
printf("%c", str[i]);
// 小数点加在位置(exp + 2)上
// 因为原先小数点的下标位置就是str[2],所以小数点移动到(exp + 2)的位置上
// 原小数点和E之间的数字个数是(pos - 3),因为正负号算1位,整数一位,小数点一位,现在就一共3位了
// 小数点后面的数字到指数位置pos的数字个数,就是(pos-3),因为所有的下标都是从0开始算起的,所以直接减3就可以,不用想多
// 注意,(pos-3)不能等于小数点右移位数exp
// 这里可以分两种情况,(pos-3)比exp大 和 (pos - 3)比exp小于等于
// (pos-3)比exp大,就要输出小数点
// (pos-3)比exp小于等于,就不用输出小数点
// 下面这个条件是i == exp + 2,但是外层循环的条件的 i < pos,所以如果pos比exp小,就不会执行,也就不会输出小数点
// 为什么是 i == exp + 2后输出小数点? 因为当exp非0的时候,原小数点的位置是str[2],因为exp>0,
// 所以小数点就移动到标号exp+2的数字后面,(因为下标是从0开始的)
// 要明白,str是一直没有变的!
// 第二个条件Pos - 3表示的是原小数点后的数字个数,如果个数和exp相等,则说明刚好新的小数点在最右边,也不用输出
if (i == exp + 2 && pos - 3 != exp)
{
printf("."); // 注意,小数点要用 双引号 括住!
}
}
// 如果指数exp较大,输出多余的0,假如exp是10
// 因为str字符串中,原小数点后的数字个数为(pos-3)
// 如果exp比(pos-3)大的话,则要输出多余的0
for (int i = 0; i < exp - (pos - 3); i++)
{
printf("0");
}
}
return 0;
}
B1025. 反转链表
(7.3 链表处理)
思路:
- 我们可以得到的是第1个结点的地址,结点总个数。还有除去第一个结点后,其余结点的结点地址和该结点保存的整数数据和该结点的下一个结点的地址。
注意点:
- scanf输入的时候,假如输入的case中有换行,每一行在"%d"中的后面是不用加换行符\n的,但是printf需要。
- next地址只有在输入过程,也就是形成单链表的过程中有用。在输出的时候注意下一个结点的地址不再使用next,而是使用[i + 1].address或者[j - 1].address来。是因为我们在反转链表,所以在原先输入中,单链表中5号结点后面是6号结点,输出的时候5号结点就是4号结点,所以再用next会出错!
- 要注意其中块的定义是一个完整快,然后对于输出每个块的最后一个结点的时候要进行处理,重点处理的是该块最后一个结点的下一个结点,先看看块是否是最后一个——
如果不是最后一块,就指向下一块的最后一个结点。
如果该块是最后一块,恰好是该最后一个完整块的最后一个结点还是整体的最后一个结点(之前判断的则是否是当前该完整块的最后一个结点),那么输出-1。
如果该最后一个完整块的最后一个结点并不是整体的最后一个结点,剩下不完整的块则按原先的顺序输出。
完整代码(注释有详细解释):
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;
// 定义静态链表(步骤1)
struct Node
{
int address, data, next;
// 结点在链表上的序号,无效结点记为maxn
int order;
}node[maxn];
bool cmp(Node a, Node b)
{
// 按order从小到大对结点进行排序
return a.order < b.order;
}
int main()
{
// 初始化
for (int i = 0; i < maxn; i++)
{
// 初始化全部为无效结点
node[i].order = maxn;
}
// 起始地址、结点个数、步长、当前结点的地址
int begin, n, K, address;
scanf("%d%d%d", &begin, &n, &K);
for (int i = 0; i < n; i++)
{
scanf("%d", &address);
// scanf输入的时候,每一行在""中是不用加换行符\n的,但是Printf需要
scanf("%d%d", &node[address].data, &node[address].next);
node[address].address = address;
}
// count计数有效结点的数目
int p = begin;
int count = 0;
// 遍历链表找出单链表的所有有效结点
while (p != -1)
{
// 结点在单链表中的序号
node[p].order = count++;
// 下一个结点
p = node[p].next;
}
// 按单链表从头到尾顺序排列
sort(node, node + maxn, cmp);
// 有效结点为前count个结点,为了书写方便,将count赋值给n
n = count;
// 单链表已经形成,下面按题目要求的输出
// 枚举完整的n / K块
for (int i = 0; i < n / K; i++)
{
// 第i块倒着输出
// 因为是反转嘛,所以倒着输出
for (int j = (i + 1) * K - 1; j > i* K; j--)
{
// 这里为什么是 j > i * K 而不是 j >= i * K 呢?
// 假如i是0,则只输出了3 2 1号结点,0号结点没有输出,因为0号结点在后面根据第i块是否是最后一块来分别处理
printf("%05d %d %05d\n", node[j].address, node[j].data, node[j - 1].address);
}
// 下面是每一块的最后一个结点的next地址的处理
printf("%05d %d ", node[i * K].address, node[i * K].data);
// 如果不是最后一块,就指向下一块的最后一个结点
if (i < n / K - 1)
{
printf("%05d\n", node[(i + 2) * K - 1].address); // 为什么是i+2呢?因为是下一块的最后一个结点,比如i=0,那么下一个结点编号就是7
}
// 如果是最后一块,能称为块,那么一定是完整的
else
{
// 恰好是最后一个结点,输出-1
if (n % K == 0) // 比如n和K都是4
{
printf("-1\n");
}
// 剩下不完整的块则按原先的顺序输出
else
{
printf("%d\n", node[(i + 1) * K].address); // i + 1 的意思就是第i块输入完后,后面紧跟的第一个结点编号
for (int i = n / K * K; i < n; i++) // 只要明白下标是0开始的,n=7 K = 4,模拟一下就可以理解了
{
printf("%05d %d ", node[i].address, node[i].data);
if (i < n - 1) // 不是最后一个结点
{
printf("%05d\n", node[i + 1].address); // 输出时候是不用next的,next是输入时候用到的,也就是使用结点形成单链表的时候
// 输出时候反转了或者按顺序输出了, 所以用node[i+1]/[j-1].address就好了
}
else
{
// 是最后一个结点
printf("-1\n");
}
}
}
}
}
return 0;
}