Day25 洛谷 提高- 1007

零基础洛谷刷题记录

Day01 2024.11.18
Day02 2024.11.25
Day03 2024.11.26
Day04 2024.11.28
Day05 2024.11.29
Day06 2024 12.02
Day07 2024.12.03
Day08 2024 12 05
Day09 2024.12.07
Day10 2024.12.09
Day11 2024.12.10
Day12 2024.12.12
Day13 2024.12.16
Day14 2024.12.17
Day15 2024.12.18
Day16 2024.12.19
Day17 2024.12.21
Day18 2024.12.23
Day19 2024.12.24
Day20 2024.12.25
Day21 2024.12.26
Day22 2025.01.19
Day23 2025.01.21
Day24 2025.02.01
Day25 2025.02.04

---

---

独木桥

1007：题目描述

战争已经进入到紧要时间。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。士兵们十分愤怒，因为这座独木桥十分狭窄，只能容纳 1 个人通过。假如有 2 个人相向而行在桥上相遇，那么他们 2 个人将无法绕过对方，只能有 1 个人回头下桥，让另一个人先通过。但是，可以有多个人同时呆在同一个位置。
突然，你收到从指挥部发来的信息，敌军的轰炸机正朝着你所在的独木桥飞来！为了安全，你的部队必须撤下独木桥。独木桥的长度为 L，士兵们只能呆在坐标为整数的地方。所有士兵的速度都为 1，但一个士兵某一时刻来到了坐标为 0 或 L+1 的位置，他就离开了独木桥。

每个士兵都有一个初始面对的方向，他们会以匀速朝着这个方向行走，中途不会自己改变方向。但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。转身不需要任何的时间。

由于先前的愤怒，你已不能控制你的士兵。甚至，你连每个士兵初始面对的方向都不知道。因此，你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外，总部也在安排阻拦敌人的进攻，因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。

1007：AC代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<math.h>int main()
{int brige_length;//桥的长度scanf("%d", &brige_length);int number;//士兵人数scanf("%d", &number);static int weizhi[5005] = { 0 };//士兵坐标static int num[5005] = { 0 };//坐标士兵for (int i = 0; i < number; i++){scanf("%d", &weizhi[i]);num[weizhi[i]]++;}int max_time = 0;int min_time = 0;if (number == 0 || brige_length == 1){printf("0 0\n");return 0;}//如果桥长为偶数if (brige_length % 2 == 0){//最短时间的计算min_time = brige_length / 2;int i = 0;while (num[brige_length / 2 - i] == 0 && num[brige_length / 2 + 1 + i] == 0){min_time--;i++;}}//如果桥长为奇数if (brige_length % 2 == 1){//最短时间的计算min_time = brige_length / 2;int i = 0;if (num[brige_length / 2 + 1]){min_time = brige_length / 2 + 1;}else{while (num[brige_length / 2 - i] == 0&& num[brige_length / 2 + 2 + i] == 0){min_time--;i++;}}}//最长时间的计算int max_zuo = brige_length;int max_you = brige_length;int j = 1;while (num[j] == 0){max_zuo--;j++;}j = 0;while (num[brige_length - j] == 0){max_you--;j++;}max_time = max_zuo > max_you ? max_zuo : max_you;printf("%d %d\n", min_time, max_time);return 0;
}

1007：学习成果

• 神奇的deepseek成功写出来了！
• 对于最大时间的计算是看题解得到的，原来是交换相当于继续往前走，果然是有捷径而不需要疯狂讨论的
• 洛谷题也需要进行代码健壮性检验，这题没有分类出人数为0的情况的话，会出现RE的情况
• 并没有想象的那么难，不是代码难，而是逻辑变难，对数学的要求变高了！