当前位置：网站首页>hdu1495 非常可乐 (广搜)

hdu1495 非常可乐 (广搜)

2022-08-08 18:58:00 【51CTO】

非常可乐

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

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

Sample Output

Author

       
       seeyou
      
1.

Source

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

Recommend

LL | We have carefully selected several similar problems for you: 1072 1372 1180 1240 1026

Statistic | Submit | Discuss | Note

类似三个水杯倒水。

假如i向j倒水有以下规则：

如果i水杯内水的容量大于j水杯内倒满所需的容量x，则i水杯倒水后的容量为：i-x,j水杯倒水后容量为:j+x
如果i水杯内水的容量小于j水杯内倒满所需的容量x，则i水杯倒水后的容量为：0,j水杯倒水后容量为:j+x

       
       #include <stdio.h>
       
       #include <queue>
       
       #include <string.h>
       
       using 
       
       namespace 
       
       std;
       
       struct 
       
       node
       
{
       
       int 
       
       a[
       
       3];
       
       //当前水杯的状态
       
       int 
       
       step;
       
       friend 
       
       bool 
       
       operator
       
       <(
       
       node 
       
       a,
       
       node 
       
       b)
       
  {
       
       return 
       
       a.
       
       step
       
       >
       
       b.
       
       step;
       
  }
       
};
       
       int 
       
       A[
       
       3];
       
       //水杯容量
       
       int 
       
       aim;
       
       //求解目标A[0]/2
       
       void 
       
       bfs()
       
{
       
       priority_queue
       
       <
       
       node
       
       >
       
       s;
       
       node 
       
       node1,
       
       node2;
       
       bool 
       
       vis[
       
       105][
       
       105][
       
       105];
       
       memset(
       
       vis,
       
       false,
       
       sizeof(
       
       vis));
       
       node1.
       
       a[
       
       0]
       
       =
       
       A[
       
       0];
       
       node1.
       
       a[
       
       1]
       
       =
       
       node1.
       
       a[
       
       2]
       
       =
       
       node1.
       
       step
       
       =
       
       0;
       
       s.
       
       push(
       
       node1);
       
       int 
       
       res
       
       =-
       
       1;
       
       while(
       
       !
       
       s.
       
       empty())
       
  {
       
       node1
       
       =
       
       node2
       
       =
       
       s.
       
       top();
       
       s.
       
       pop();
       
       // printf("%d %d %d %d\n",node1.a[0],node1.a[1],node1.a[2],node1.step);
       
       if(
       
       vis[
       
       node1.
       
       a[
       
       0]][
       
       node1.
       
       a[
       
       1]][
       
       node1.
       
       a[
       
       2]]) 
       
       continue;
       
       vis[
       
       node1.
       
       a[
       
       0]][
       
       node1.
       
       a[
       
       1]][
       
       node1.
       
       a[
       
       2]]
       
       =
       
       true;
       
       if((
       
       node1.
       
       a[
       
       0]
       
       ==
       
       aim
       
       &&
       
       node1.
       
       a[
       
       1]
       
       ==
       
       aim)
       
       ||(
       
       node1.
       
       a[
       
       0]
       
       ==
       
       aim
       
       &&
       
       node1.
       
       a[
       
       2]
       
       ==
       
       aim)
       
       ||(
       
       node1.
       
       a[
       
       1]
       
       ==
       
       aim
       
       &&
       
       node1.
       
       a[
       
       2]
       
       ==
       
       aim))
       
    {
       
       res
       
       =
       
       node1.
       
       step;
       
       break;
       
    }
       
       //i杯向j杯倒水 
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       3;
       
       i
       
       ++)
       
    {
       
       if(
       
       node1.
       
       a[
       
       i]
       
       ==
       
       0) 
       
       continue;
       
       for(
       
       int 
       
       j
       
       =
       
       0;
       
       j
       
       <
       
       3;
       
       j
       
       ++)
       
      {
       
       if(
       
       i
       
       ==
       
       j
       
       ||
       
       node1.
       
       a[
       
       j]
       
       ==
       
       A[
       
       j]) 
       
       continue;
       
       node1
       
       =
       
       node2;
       
       //x表示j水杯还可以倒入的水量 
       
       int 
       
       x
       
       =
       
       A[
       
       j]
       
       -
       
       node1.
       
       a[
       
       j]; 
       
       //如果i杯的水量大于j杯所需的水量 
       
       if(
       
       node1.
       
       a[
       
       i]
       
       >
       
       x)
       
        {
       
       node1.
       
       a[
       
       i]
       
       -=
       
       x;
       
       node1.
       
       a[
       
       j]
       
       =
       
       A[
       
       j];
       
        }
       
       else
       
        {
       
       node1.
       
       a[
       
       j]
       
       +=
       
       node1.
       
       a[
       
       i];
       
       node1.
       
       a[
       
       i]
       
       =
       
       0;
       
        }
       
       if(
       
       vis[
       
       node1.
       
       a[
       
       0]][
       
       node1.
       
       a[
       
       1]][
       
       node1.
       
       a[
       
       2]]) 
       
       continue;
       
       node1.
       
       step
       
       ++;
       
       s.
       
       push(
       
       node1);
       
      }
       
    }
       
  }
       
       if(
       
       res
       
       ==-
       
       1)
       
       puts(
       
       "NO");
       
       else
       
       printf(
       
       "%d\n",
       
       res);
       
}
       
       int 
       
       main()
       
{
       
       // freopen("in.txt","r",stdin);
       
       while(
       
       ~scanf(
       
       "%d %d %d",
       
       &
       
       A[
       
       0],
       
       &
       
       A[
       
       1],
       
       &
       
       A[
       
       2]))
       
  {
       
       if(
       
       A[
       
       0]
       
       ==
       
       0
       
       ||
       
       A[
       
       1]
       
       ==
       
       0
       
       ||
       
       A[
       
       2]
       
       ==
       
       0)
       
       break;
       
       //如果是奇数 肯定无法均分 
       
       if(
       
       A[
       
       0]
       
       %
       
       2)
       
    {
       
       puts(
       
       "NO");  
       
       continue;
       
    }
       
       aim
       
       =
       
       A[
       
       0]
       
       /
       
       2;
       
       bfs();
       
  }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15742657/5557098

当前位置：网站首页>hdu1495 非常可乐 (广搜)

hdu1495 非常可乐 (广搜)

非常可乐

边栏推荐

猜你喜欢

随机推荐