小码君喝牛奶:思路+难点+题解

*这篇题解借鉴了AC君的题解思路,但是部分内容会讲得较为详细,如果只是思路不清楚,可以直接看AC君的题解

一.思路与难点
题目 : (因为题目本身没有特别繁琐,就直接把重点了解一下就好)
有三个容量分别为a,b,c的桶. 最开始, a,b桶为空, c桶装满牛奶.
本篇文章中会将容量为a,b,c的桶分别命名为a,b,c.
小码君会把牛奶从一个桶倒到另一个桶中,直到被灌桶装满或原桶为空.
当然每一次灌注都是完全的。由于节约，牛奶不会有丢失.
想求在a桶为空时,c桶的所有可能性(升序)

先说难点:
1.如何模拟倒牛奶的过程?
2.如何确保倒牛奶的过程中没有重复过程?
3.如何正确的存储所有符合要求的答案?

难点的相应思路:
1.如何模拟倒牛奶的过程?
在DFS的函数中设置三个参数x,y,z(或者a1,b1,c1也可以) 来对应a,b,c三个桶的牛奶量

void dfs(int x,int y,int z){
    //过程
}

如果想要倒牛奶,一共有六种可能:
(a,b) (a,c) (b,a) (b,c) (c,a) (c,b)
*(a,b)代表将a桶中的牛奶倒入b桶中 前提:a桶中有牛奶且b桶还能倒牛奶
然后要决定倒入牛奶的量
注意前文题目:
小码君会把牛奶从一个桶倒到另一个桶中,直到被灌桶装满或原桶为空
还是以(a,b)为例
设b桶能倒入的牛奶量为: b-y (y是b桶中,牛奶的数量)
设a桶能倒入b桶的牛奶量为: x (x是a桶中牛奶的量)
那么,最终能从a桶倒入b桶中的牛奶量为:

min(x,b-y)

因为要保证最终倒入b桶的牛奶量小于等于b-y(不然会浪费,溢出)

2.如何确保倒牛奶的过程中没有重复过程?
可以用二维/三位数组,(bool/int都可以),比如:

int vis[21][21]

每当进行了一次倒牛奶操作:

vis[x][y]=1;//x,y分别是a,b桶中的牛奶量

可以只用二维数组的原因是牛奶的总量是不变的,而且只有三个桶.
所以当a,b桶中的牛奶数量确定,c桶中的牛奶数量其实也是确定的.

3.如何正确的存储所有符合要求的答案?
这里考虑到如果直接用数组存然后排序的话,可能就会有重复的现象,所以可以用一个bool或者int数组来当桶

int ans[21];

如果有符合条件的答案就记录

if(x==0&&z!=0){
    //x是a桶的牛奶量,z是c桶的牛奶量
	ans[z]=1;
}

最后输出时,直接判断ans[i]是否为1即可,如果为1,输出i

for(int i=1;i<=c;i++){
    //这里循环到c是因为c桶中的容量最多能到c
	if(ans[i])cout<<i<<" ";
}

二.题解
*因为前面已经把大量重要代码放出,这里就不放挖空题解了
*此代码并不是格式上,时间上,空间上的最优代码;但是比较容易理解;后期可能会放优化代码.

#include<bits/stdc++.h>
using namespace std;
bool vis[21][21];
int ans[21];
int sum=0;
int a,b,c;
void dfs(int x,int y,int z){
	if(x==0){
		ans[z]=1;
	}
	if(x&&b-y>0){
		int ans1=min(x,b-y);
		x-=ans1;
		y+=ans1;
		if(!vis[x][y]){
			vis[x][y]=1;
			dfs(x,y,z);
		}else{
			x+=ans1;
			y-=ans1;
		}
	}
	if(x&&c-z>0){
		int ans1=min(x,c-z);
		x-=ans1;
		z+=ans1;
		if(!vis[x][y]){
			vis[x][y]=1;
			dfs(x,y,z);
		}else{
			x+=ans1;
			z-=ans1;
		}
	}
	if(y&&a-x>0){
		int ans1=min(y,a-x);
		y-=ans1;
		x+=ans1;
		if(!vis[x][y]){
			vis[x][y]=1;
			dfs(x,y,z);
		}else{
			y+=ans1;
			x-=ans1;
		}
	}
	if(y&&c-z>0){
		int ans1=min(y,c-z);
		y-=ans1;
		z+=ans1;
		if(!vis[x][y]){
			vis[x][y]=1;
			dfs(x,y,z);
		}else{
			y+=ans1;
			z-=ans1;
		}
	}
	if(z&&a-x>0){
		int ans1=min(z,a-x);
		z-=ans1;
		x+=ans1;
		if(!vis[x][y]){
			vis[x][y]=1;
			dfs(x,y,z);
		}else{
			z+=ans1;
			x-=ans1;
		}
	}
	if(z&&b-y>0){
		int ans1=min(z,b-y);
		z-=ans1;
		y+=ans1;
		if(!vis[x][y]){
			vis[x][y]=1;
			dfs(x,y,z);
		}else{
			z+=ans1;
			y-=ans1;
		}
	}
}
int main(){
	cin>>a>>b>>c;
    vis[0][0]=1;
	dfs(0,0,c);
	for(int i=0;i<=c;i++){
		if(ans[i])cout<<i<<" ";
	}
}

完