hdu 1495 非常可乐

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 24840 Accepted Submission(s): 9666

Problem Description

大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升可乐的体积为S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。

Input

三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。

Output

如果能平分的话请输出最少要倒的次数，否则输出"NO"。

Sample Input

7 4 3 4 1 3 0 0 0

Sample Output

NO 3

Author

seeyou

Source

“2006校园文化活动月”之“校庆杯”大学生程序设计竞赛暨杭州电子科技大学第四届大学生程序设计竞赛

Recommend

LL | We have carefully selected several similar problems for you: 1175 1253 1072 1372 1180

一开始还想能不能通过思维找出最优答案，发现很难，于是就得遍历各种情况，找出最小步数，类似二维图的最短路，bfs遍历各种情况，当发现出现了哪个杯子或瓶子中有S/2可乐就可以输出答案了，但是要求是得到两个S/2的答案，即有一个杯子必须是空的，所以返回的答案还要判断是否有空的，如果不是还需要加一步来完成。这里用一个3元素数组代替S,N,M，order是个顺序数组，即order[i][0]往order[i][1]里倒，order[i][2]保持不变。对于访问过的情况，我们通过映射记录，即check函数。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct sta {
    int ar[3];
    sta(){}
    sta(int a,int b,int c) {
        ar[0] = a;
        ar[1] = b;
        ar[2] = c;
    }
};
typedef pair<sta,int> pa;
int ar[3];
int order[6][3] = {0,1,2,0,2,1,1,0,2,1,2,0,2,0,1,2,1,0};
bool vis[1000001];
bool check(const sta &temp) {
    int d = temp.ar[0] * 10000 + temp.ar[1] * 100 + temp.ar[2];
    bool e = vis[d];
    vis[d] = true;
    return e;
}
sta change(const sta &temp,int a,int b,int c) {
    sta temp1;
    if(temp.ar[a] > ar[b] - temp.ar[b]) {
        temp1.ar[a] = temp.ar[a] - ar[b] + temp.ar[b];
        temp1.ar[b] = ar[b];
    }
    else {
        temp1.ar[a] = 0;
        temp1.ar[b] = temp.ar[b] + temp.ar[a];
    }
    temp1.ar[c] = temp.ar[c];
    return temp1;
}
int bfs() {
    if(ar[0] % 2) return 0;
    queue<pa> q;
    q.push(pa(sta(ar[0],0,0),0));
    check(sta(ar[0],0,0));
    while(!q.empty()) {
        sta temp = q.front().first,temp1;
        int times = q.front().second;
        q.pop();
        for(int i = 0;i < 6;i ++) {
            temp1 = change(temp,order[i][0],order[i][1],order[i][2]);
            if(temp1.ar[0] == ar[0] / 2 || temp1.ar[1] == ar[0] / 2 || temp1.ar[2] == ar[0] / 2) return times + 1 + (temp1.ar[0] && temp1.ar[1] && temp1.ar[2]);
            if(!check(temp1)) q.push(pa(temp1,times + 1));
        }
    }
    return 0;
}
int main() {
    while(scanf("%d%d%d",&ar[0],&ar[1],&ar[2]) && ar[0] && ar[1] && ar[2]) {
        memset(vis,false,sizeof(vis));
        int ans = bfs();
        if(ans)printf("%d
",ans);
        else printf("NO
");
    }
}