这道题TLE了很多次,原来一直以为将数字化为最简可以让运算更快,但是去了简化之后才发现,真正耗时的就是化简....还和队友学到了用状态少直接数组模拟刚就能过...
本题大意:给出可乐的体积v1,给出两个杯子v2和v3,要求v2 + v3 == v1,每次只能从一个杯子倒到另一个杯子,问最少倒多少次可以将可乐平分。
思路:最后可乐肯定在可乐瓶和大杯子里面,直接BFS暴搜就行了。
参考代码:
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std; struct node {
int cur[], step;
} now, Next; const int maxn = + ;
int v[];
int ans, t;
bool flag;
bool vis[maxn][maxn][maxn]; void bfs() {
if(v[] & ) {
flag = false;
return;
}
queue <node> Q;
now.cur[] = v[], now.cur[] = , now.cur[] = , now.step = ;
vis[v[]][][] = true;
Q.push(now);
while(!Q.empty()) {
now = Q.front();
Q.pop();
if(now.cur[] == now.cur[] && now.cur[] == ) {
ans = now.step;
return;
}
for(int i = ; i < ; i ++) {//i -> j
for(int j = ; j < ; j ++) {
if(i != j) {
Next = now;
t = now.cur[i] + now.cur[j];
if(t > v[j]) Next.cur[j] = v[j];
else Next.cur[j] = t;
Next.cur[i] = t - Next.cur[j];
if(!vis[Next.cur[]][Next.cur[]][Next.cur[]]) {
Next.step = now.step + ;
Q.push(Next);
vis[Next.cur[]][Next.cur[]][Next.cur[]] = true;
}
}
}
}
}
flag = false;
} int main () {
while(~scanf("%d %d %d", &v[], &v[], &v[])) {
memset(vis, false, sizeof(vis));
if(v[] == && v[] == && now.cur[] == ) break;
flag = true, ans = ;
if(v[] < v[]) {
t = v[];
v[] = v[];
v[] = t;
}
bfs();
if(flag) printf("%d\n", ans);
else printf("NO\n");
}
return ;
}
下面这个代码的效率要高一点,区别在于倒水方式不同。
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std; struct node {
int cur[], step;
} now, Next; const int maxn = + ;
int v[];
int ans, t;
bool flag;
bool vis[maxn][maxn][maxn]; void bfs() {
if(v[] & ) {
flag = false;
return;
}
queue <node> Q;
now.cur[] = v[], now.cur[] = , now.cur[] = , now.step = ;
vis[v[]][][] = true;
Q.push(now);
while(!Q.empty()) {
now = Q.front();
Q.pop();
if(now.cur[] == now.cur[] && now.cur[] == ) {
ans = now.step;
return;
}
for(int i = ; i < ; i ++) {//i -> j
for(int j = ; j < ; j ++) {
if(i != j) {
Next = now;
if(j == ) {
Next.cur[j] = now.cur[j] + now.cur[i];
Next.cur[i] = ;
} else if(j == ) {
t = v[] - now.cur[j];
Next.cur[i] = now.cur[i] - t;
Next.cur[i] = Next.cur[i] > ? Next.cur[i] : ;
Next.cur[j] = now.cur[j] + now.cur[i];
Next.cur[j] = Next.cur[j] < v[] ? Next.cur[j] : v[];
} else {
t = v[] - now.cur[j];
Next.cur[i] = now.cur[i] - t;
Next.cur[i] = Next.cur[i] > ? Next.cur[i] : ;
Next.cur[j] = now.cur[j] + now.cur[i];
Next.cur[j] = Next.cur[j] < v[] ? Next.cur[j] : v[];
}
if(!vis[Next.cur[]][Next.cur[]][Next.cur[]]) {
Next.step = now.step + ;
Q.push(Next);
vis[Next.cur[]][Next.cur[]][Next.cur[]] = true;
}
}
}
}
}
flag = false;
} int main () {
while(~scanf("%d %d %d", &v[], &v[], &v[])) {
memset(vis, false, sizeof(vis));
if(v[] == && v[] == && now.cur[] == ) break;
flag = true, ans = ;
if(v[] < v[]) {
t = v[];
v[] = v[];
v[] = t;
}
bfs();
if(flag) printf("%d\n", ans);
else printf("NO\n");
}
return ;
}