AcWing 1355. 母亲的牛奶(每日一题)

简介: AcWing 1355. 母亲的牛奶(每日一题)

原题链接1355. 母亲的牛奶 - AcWing题库

题目:

农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。

最开始桶 A和桶 B都是空的,而桶 C里装满了牛奶。

有时,约翰会将牛奶从一个桶倒到另一个桶中,直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。

这一过程中间不能有任何停顿,并且不会有任何牛奶的浪费。

请你编写一个程序判断,当 A桶是空的时候,C桶中可能包含多少升牛奶,找出所有的可能情况。

输入格式

共一行,包含三个整数 A,B,C。

输出格式

共一行,包含若干个整数,表示 C桶中牛奶存量的所有可能情况,请将这些数字按升序排列

数据范围

1≤A,B,C≤20

输入样例1:

8 9 10

输出样例1:

1 2 8 9 10

输入样例2:

2 5 10
5 6 7 8 9 10
难度:中等
时/空限制:1s / 64MB
总通过数:2387
总尝试数:3215
来源:

usaco training 1.5

算法标签

BFS DFS


解题思路:

此题主要是利用DFS、BFS搜索,题目数据量很小,时间复杂度为O(ABC),DFS、BFS都可以过。一个状态(a,b,c)可以有6种方案,可以a往b倒、a往c倒、b往a倒、b往c倒、c往a倒、c往b倒,用搜索把六种状态都都搜索一遍,用vis三维数组标记是否被搜过,最后再找一下A桶为0,C桶的体积即可。

这里解释一下样例,开始我也没看懂什么意思,c->a表示C桶往A桶倒每一个状态都可以向下转移搜索,红色框表示符合题意A=0。


DFS版:
 #include<iostream>
using namespace std;
const int N = 25;
int A,B,C;
bool vis[N][N][N];
void dfs(int a,int b,int c){//abc表示此时三个桶牛奶的体积
    if(vis[a][b][c])return;//重复搜索
    vis[a][b][c]=true;
    if(a>B-b)dfs(a-B+b,B,c);//a往b里面倒
    else dfs(0,a+b,c);
    if(a>C-c)dfs(a-C+c,b,C);//a往c里面倒
    else dfs(0,b,a+c);
    if(b>A-a)dfs(A,b-A+a,c);//b往a里面倒
    else dfs(a+b,0,c);
    if(b>C-c)dfs(a,b-C+c,C);//b往c里面倒
    else dfs(a,0,b+c);
    if(c>A-a)dfs(A,b,c-A+a);//c往a里面倒
    else dfs(a+c,b,0);
    if(c>B-b)dfs(a,B,c-B+b);//c往b里面倒
    else dfs(a,b+c,0);
}
int main(){
    cin>>A>>B>>C;
    dfs(0,0,C);
    for(int i=0;i<=C;i++){//升序输出,先枚举C桶
        for(int j=0;j<=B;j++){
            if(vis[0][j][i]){
                cout<<i<<" ";
                break;
            }
        }
    }
    return 0;
}
 
BFS版:
#include<iostream>
#include<queue>
using namespace std;
const int N=25;
int A,B,C;
bool vis[N][N][N];
struct node{
  int a,b,c;
};
queue<node> q;
void insert(int a,int b,int c){
  if(!vis[a][b][c]){
    q.push({a,b,c});
    vis[a][b][c]=true;
  }
}
void bfs(){
  while(q.size()){
    auto t=q.front();
    q.pop();
    int x=t.a,y=t.b,z=t.c;//把六种情况枚举一遍
    insert(x-min(x,B-y),min(B,x+y),z);//a往b里面倒
    insert(x-min(x,C-z),y,min(C,x+z));//a往c里面倒
    insert(min(A,x+y),y-min(y,A-x),z);//b往a里面倒
    insert(x,y-min(y,C-z),min(y+z,C));//b往c里面倒
    insert(min(x+z,A),y,z-min(z,A-x));//c往a里面倒
    insert(x,min(B,y+z),z-min(z,B-y));//c往b里面倒
  }
}
int main(){
  cin>>A>>B>>C;
  q.push({0,0,C});
  vis[0][0][C]=true;
  bfs();
  for(int i=0;i<=C;i++){
    for(int j=0;j<=B;j++){
      if(vis[0][j][i]){
        cout<<i<<" ";
        break;
      }
    }
  }
  return 0;
}


总结:

主要考察DFS、BFS。记住板子,把自己想得思路往上写即可。此题最难的地方就是一个状态的六种转移方式。只要弄明白了六种转移方式,此题就迎刃而解了。文章尚有不足,若有错误地地方请大家指出,一起进步。

相关文章
|
2月前
|
算法
AcWing 1343. 挤牛奶(每日一题)
AcWing 1343. 挤牛奶(每日一题)
|
2月前
acwing 1098 城堡
acwing 1098 城堡
14 0
AcWing 2060. 奶牛选美(每日一题)
AcWing 2060. 奶牛选美(每日一题)
【LeetCode每日一题】找(一只或者多只)单身狗
【LeetCode每日一题】找(一只或者多只)单身狗
103 1
【LeetCode每日一题】找(一只或者多只)单身狗
|
算法 Cloud Native
【刷题日记】875. 爱吃香蕉的珂珂
本次刷题日记的第 57 篇,力扣题为:875. 爱吃香蕉的珂珂,中等
150 0
【刷题日记】875. 爱吃香蕉的珂珂
|
存储 算法 Java
【AcWing每日一题】4818. 奶牛大学
【AcWing每日一题】4818. 奶牛大学
119 0
|
测试技术 C++ Python
糖果-蓝桥杯19省赛
糖果-蓝桥杯19省赛
106 0
蓝桥杯:二分法求分巧克力
蓝桥杯:二分法求分巧克力
68 0
|
算法 C++ Python
每日算法系列【LeetCode 875】爱吃香蕉的珂珂
每日算法系列【LeetCode 875】爱吃香蕉的珂珂
107 0
|
人工智能
【寒假每日一题】AcWing 4700. 何以包邮?
目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 0-1背包问题
142 0

相关实验场景

更多