题目描述
blablabla
样例
#include<bits/stdc++.h>
#define int long long //longlong型中间要有空格
#define INF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
using namespace std;
const int N=21,M=N*N*N; //0-20,共21种状态
int A,B,C;
bool st[N][N][N];//判断是否遍历过,里面的三个数是桶中牛奶的量
struct Node //这个结构体代表树中的点,即每一次倒牛奶后的状态
{
int a,b,c; //每个状态都有 三个桶中牛奶的数量
} q[M]; //每个桶有21种状态,总共有21*21*21种状态
void bfs()
{
int hh=0,tt=0; //定义起点与终点
q[0]={0,0,C}; //初始状态 AB没有牛奶,C有牛奶
st[0][0][C]=true; //改变该点的状态
int W[3]={A,B,C}; //三个桶的容量
//bfs
while(hh<=tt)
{
auto t=q[hh++]; //取队头元素 t自动是 q对应的结构体
//先取用h,再进行加一操作
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(i!=j) //不能往自己桶里倒,从i向j中倒入
{
int w[3]={t.a,t.b,t.c}; //此时三个桶里有多少奶
int r=min(w[i],W[j]-w[j]); //每次倒入的奶不能超出i桶中的奶量,也不能从j桶中溢出
w[i]-=r,w[j]+=r; //执行倒奶操作
int a=w[0],b=w[1],c=w[2]; //倒完奶后,三个桶里奶的量
if(!st[a][b][c]) //如果之前没有遍历过,则
{
st[a][b][c]=true;
q[++tt]={a,b,c}; //把该状态加入队尾,注意先tt加一,不然会覆盖原状态
//下一次循环时, 该状态作为起始状态
}
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>A>>B>>C;
bfs();
for(int c=0;c<=C;c++) //因为输出从小到大,所以可以从0开始遍历C
for(int b=0;b<=B;b++)
if (st[0][b][c]) //最后A中没有奶,C中有多少奶,B中就要有剩下数量的奶,所以也要循环B
{
cout<<c<<" ";
break;
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla