羊、狼、农夫都在岸边，当羊的数量小于狼的数量时，狼会攻击羊，农夫则会损失羊。农夫有一艘容量固定的船，能够承载固定数量的动物。
要求求出不损失羊情况下将全部羊和狼运到对岸需要的最小次数。
只计算农夫去对岸的次数，回程时农夫不会运送羊和狼。
备注：农夫在或农夫离开后羊的数量大于狼的数量时狼不会攻击羊。
第一行输入为 ，，， 分别代表羊的数量，狼的数量，小船的容量。
输出不损失羊情况下将全部羊和狼运到对岸需要的最小次数（若无法满足条件则输出 0 ）。
5 3 3
3
第一次运2只狼
第二次运3只羊
第三次运2只羊和1只狼
5 4 1
0
如果找不到不损失羊的运送方案，输出0
本题的目标是在不损失羊的情况下，求出将所有羊和狼运到对岸所需的最小次数。我们需要注意的是，每次运动时，羊的数量必须大于等于狼的数量，以避免羊被狼攻击。
首先检查边界条件。如果船的容量为1，那么只有当狼的数量为0时，农夫才能将羊运到对岸，所需次数为羊的数量。否则输出0。
其次，我们需要确保初始状态下，狼的数量不大于羊的数量，否则无法满足题目要求，输出0。
初始化步数为0，剩余的羊和狼的数量分别等于输入的羊和狼的数量。
当剩余的羊和狼都大于0时，执行以下操作：
a. 如果剩余羊的数量大于等于剩余狼的数量，农夫运送尽可能多的羊，但不超过船的容量。然后从剩余的羊中减去运送的数量。
b. 否则，农夫运送尽可能多的狼，但不超过船的容量。然后从剩余的狼中减去运送的数量。
c. 如果在运送后剩余的狼数量大于剩余的羊数量且剩余的羊数量大于0，输出0，因为在这种情况下，羊会被狼攻击。
d. 最后，增加步数。
返回步数作为解。
时间复杂度：本算法的时间复杂度为O(min(sheep, wolf))，因为在最坏的情况下，我们需要运送羊和狼的最小数量的次数。然而，在实际问题中，羊和狼的数量通常较小，因此算法的执行速度相对较快。
空间复杂度：本算法的空间复杂度为O(1)，因为我们仅使用了几个变量来存储羊、狼和船的相关数量以及步数。这意味着算法在空间上是高效的。
#include <stdio.h>
int min_steps(int sheep, int wolf, int capacity) {
if (capacity == 1) {
return wolf > 0 ? 0 : sheep;
}
if (wolf > sheep) {
return 0;
}
int steps = 0;
int remaining_sheep = sheep;
int remaining_wolf = wolf;
while (remaining_sheep > 0 || remaining_wolf > 0) {
if (remaining_sheep >= remaining_wolf) {
int to_carry = remaining_sheep <= capacity ? remaining_sheep : capacity;
remaining_sheep -= to_carry;
} else {
int to_carry = remaining_wolf <= capacity ? remaining_wolf : capacity;
remaining_wolf -= to_carry;
}
if (remaining_wolf > remaining_sheep && remaining_sheep > 0) {
return 0;
}
steps++;
}
return steps;
}
int main() {
int sheep, wolf, capacity;
scanf("%d %d %d", &sheep, &wolf, &capacity);
int steps = min_steps(sheep, wolf, capacity);
printf("%d\n", steps);
return 0;
}
#include <iostream>
int min_steps(int sheep, int wolf, int capacity) {
if (capacity == 1) {
return wolf > 0 ? 0 : sheep;
}
if (wolf > sheep) {
return 0;
}
int steps = 0;
int remaining_sheep = sheep;
int remaining_wolf = wolf;
while (remaining_sheep > 0 || remaining_wolf > 0) {
if (remaining_sheep >= remaining_wolf) {
int to_carry = remaining_sheep <= capacity ? remaining_sheep : capacity;
remaining_sheep -= to_carry;
} else {
int to_carry = remaining_wolf <= capacity ? remaining_wolf : capacity;
remaining_wolf -= to_carry;
}
if (remaining_wolf > remaining_sheep && remaining_sheep > 0) {
return 0;
}
steps++;
}
return steps;
}
int main() {
int sheep, wolf, capacity;
std::cin >> sheep >> wolf >> capacity;
int steps = min_steps(sheep, wolf, capacity);
std::cout << steps << std::endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static int minSteps(int sheep, int wolf, int capacity) {
if (capacity == 1) {
return wolf > 0 ? 0 : sheep;
}
if (wolf > sheep) {
return 0;
}
int steps = 0;
int remainingSheep = sheep;
int remainingWolf = wolf;
while (remainingSheep > 0 || remainingWolf > 0) {
if (remainingSheep >= remainingWolf) {
int toCarry = remainingSheep <= capacity ? remainingSheep : capacity;
remainingSheep -= toCarry;
} else {
int toCarry = remainingWolf <= capacity ? remainingWolf : capacity;
remainingWolf -= toCarry;
}
if (remainingWolf > remainingSheep && remainingSheep > 0) {
return 0;
}
steps++;
}
return steps;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int sheep = scanner.nextInt();
int wolf = scanner.nextInt();
int capacity = scanner.nextInt();
int steps = minSteps(sheep, wolf, capacity);
System.out.println(steps);
}
}
def min_steps(sheep, wolf, capacity):
if capacity == 1:
return 0 if wolf > 0 else sheep
if wolf > sheep:
return 0
steps = 0
remaining_sheep = sheep
remaining_wolf = wolf
while remaining_sheep > 0 or remaining_wolf > 0:
if remaining_sheep >= remaining_wolf:
to_carry = min(remaining_sheep, capacity)
remaining_sheep -= to_carry
else:
to_carry = min(remaining_wolf, capacity)
remaining_wolf -= to_carry
if remaining_wolf > remaining_sheep and remaining_sheep > 0:
return 0
steps += 1
return steps
if __name__ == "__main__":
sheep, wolf, capacity = map(int, input().split())
steps = min_steps(sheep, wolf, capacity)
print(steps)
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
function minSteps(sheep, wolf, capacity) {
if (capacity === 1) {
return wolf > 0 ? 0 : sheep;
}
if (wolf > sheep) {
return 0;
}
let steps = 0;
let remainingSheep = sheep;
let remainingWolf = wolf;
while (remainingSheep > 0 || remainingWolf > 0) {
if (remainingSheep >= remainingWolf) {
let toCarry = Math.min(remainingSheep, capacity);
remainingSheep -= toCarry;
} else {
let toCarry = Math.min(remainingWolf, capacity);
remainingWolf -= toCarry;
}
if (remainingWolf > remainingSheep && remainingSheep > 0) {
return 0;
}
steps++;
}
return steps;
}
readline.question('', (input) => {
const [sheep, wolf, capacity] = input.split(' ').map(Number);
const steps = minSteps(sheep, wolf, capacity);
console.log(steps);
readline.close();
});
package main
import (
"fmt"
)
func minSteps(sheep, wolf, capacity int) int {
if capacity == 1 {
if wolf > 0 {
return 0
}
return sheep
}
if wolf > sheep {
return 0
}
steps := 0
remainingSheep := sheep
remainingWolf := wolf
for remainingSheep > 0 || remainingWolf > 0 {
if remainingSheep >= remainingWolf {
toCarry := min(remainingSheep, capacity)
remainingSheep -= toCarry
} else {
toCarry := min(remainingWolf, capacity)
remainingWolf -= toCarry
}
if remainingWolf > remainingSheep && remainingSheep > 0 {
return 0
}
steps++
}
return steps
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
var sheep, wolf, capacity int
fmt.Scan(&sheep, &wolf, &capacity)
steps := minSteps(sheep, wolf, capacity)
fmt.Println(steps)
}