Date：2022.02.15
題意：
大家一定覺的運動以后喝可樂是一件很愜意的事情，但是 seeyou 卻不這么認為。
因為每次當 seeyou 買了可樂以后，阿牛就要求和 seeyou 一起分享這一瓶可樂，而且一定要喝的和 seeyou 一樣多。
但 seeyou 的手中只有兩個杯子，它們的容量分別是 N 毫升和 M 毫升。
可樂的體積為 S （S<101）毫升　(正好裝滿一瓶) ，它們三個之間可以相互倒可樂 (都是沒有刻度的，且 S=N+M，101＞S＞0，N＞0，M＞0) 。
聰明的 ACMER 你們說他們能平分嗎？
如果能請輸出倒可樂的最少的次數，如果不能輸出 NO。
輸入格式
輸入包含多組測試數據。
每組數據一行，三個整數 S,N,M。
當輸入一行為 0 0 0 時，表示輸入結束。
輸出格式
每組數據輸出一行結果，如果能夠平分，則輸出倒可樂的最少的次數，否則輸出 NO。
數據范圍
S=N+M，101＞S＞0，N＞0，M＞0)
輸入樣例：
7 4 3
4 1 3
0 0 0
輸出樣例：
NO
3

思路：能平分的前提是毫升數為偶數。其次，每次倒時只有梭哈全到處去才能使最小步數最小。此外由于有三個杯子，任意兩個最終相同就跳出。
代碼如下：

#include <bits/stdc++.h> using namespace std; const int N = 110; typedef long long LL; LL w[3]; bool st[N][N][N]; struct node {LL v[3],step; }; void bfs() {memset(st,false,sizeof st);queue<node>q;q.push({w[0],0,0,0});st[w[0]][0][0]=true;while(q.size()){node t=q.front();q.pop();if(t.v[0]==0&&t.v[1]==t.v[2] || t.v[1]==0&&t.v[0]==t.v[2] || t.v[2]==0&&t.v[0]==t.v[1])//有下面那行這行固定為t.v[0]==t.v[2]&&t.v[1]==0{cout<<t.step<<endl;return;}for(int i=0;i<3;i++)for(int j=0;j<3;j++){if(i==j) continue;node tt=t;LL minn=min(tt.v[i],w[j]-tt.v[j]);tt.v[i]-=minn;tt.v[j]+=minn;if(!st[tt.v[0]][tt.v[1]][tt.v[2]]){tt.step++;q.push(tt);st[tt.v[0]][tt.v[1]][tt.v[2]]=true;}}}cout<<"NO"<<endl; } int main() {while(cin>>w[0]>>w[1]>>w[2],w[0]&&w[1]&&w[2]){//if(w[1]>w[2]) swap(w[1],w[2]);//此時，保證最后平分的是w[0]==w[2] && w[1]==0，否則討論3種情況if(w[0]%2) cout<<"NO"<<endl;else bfs();}return 0; }

總結

以上是生活随笔為你收集整理的【kuangbin】简单搜索 - 13.非常可乐【BFS】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。