HDOJ 1495 非常可乐 【BFS】

2023-11-29 23:09
文章标签 bfs 非常 hdoj 可乐 1495

本文主要是介绍HDOJ 1495 非常可乐 【BFS】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

非常可乐

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


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

分析:可以将本题看成一个隐式图,枚举所有的情况直到能够平分,或者枚举完。

代码:

#include <cstdio>
#include <queue>  //用到了优先队列
#include <cstring>
#include <algorithm>
const int M = 101;
using namespace std;bool vis[101][101][101]; //标记状态
struct node{int v[3];int step;bool operator < (const node &a) const{  return step > a.step;}
};
int hal, v[3];  //hal是一半,v数组是每个杯子的容积bool match(node a){int ans = 0;for(int i = 0; i < 3; ++ i)if(a.v[i] == hal) ++ans;if(ans == 2) return 1;  //return 0;
}int bfs(){memset(vis, 0, sizeof(vis));node st;st.v[0] = v[0]; st.v[1] = st.v[2] = 0;st.step = 0;priority_queue<node >q;q.push(st);vis[v[0]][0][0] = 1;if(match(st)) return st.step;while(!q.empty()){node temp = q.top();q.pop();for(int i = 0; i < 3; ++ i){  if(temp.v[i]){  //如果一个杯子有水,就让他往其他两个杯子倒水for(int j = 1; j < 3; ++ j){node cur = temp;int w = (i+j)%3;if(cur.v[w] < v[w]){  //倒的时候也分是不是满了,如果不满那么还需要判断能不能倒满还是不能倒满if(cur.v[i] <= (v[w]-cur.v[w])){cur.v[w] += cur.v[i]; cur.v[i] = 0;if(match(cur)) return cur.step+1;}else {cur.v[i] -= (v[w]-cur.v[w]);cur.v[w] = v[w];if(match(cur)) return cur.step+1;}if(!vis[cur.v[0]][cur.v[1]][cur.v[2]]){vis[cur.v[0]][cur.v[1]][cur.v[2]] = 1;cur.step++;q.push(cur);}}}}}} return -1;
}int main(){while(scanf("%d%d%d", &v[0], &v[1], &v[2]), v[0]||v[1]||v[2]){if(v[0]&1){printf("NO\n");continue;}else {hal = v[0]/2;int ans = bfs();if(ans >= 0) printf("%d\n", ans);else printf("NO\n");}}return 0;
}


这篇关于HDOJ 1495 非常可乐 【BFS】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/434685

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

C语言指针入门 《C语言非常道》

C语言指针入门 《C语言非常道》 作为一个程序员,我接触 C 语言有十年了。有的朋友让我推荐 C 语言的参考书,我不敢乱推荐,尤其是国内作者写的书,往往七拼八凑,漏洞百出。 但是,李忠老师的《C语言非常道》值得一读。对了,李老师有个官网,网址是: 李忠老师官网 最棒的是,有配套的教学视频,可以试看。 试看点这里 接下来言归正传,讲解指针。以下内容很多都参考了李忠老师的《C语言非

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

C#设计模式(1)——单例模式(讲解非常清楚)

一、引言 最近在学设计模式的一些内容,主要的参考书籍是《Head First 设计模式》,同时在学习过程中也查看了很多博客园中关于设计模式的一些文章的,在这里记录下我的一些学习笔记,一是为了帮助我更深入地理解设计模式,二同时可以给一些初学设计模式的朋友一些参考。首先我介绍的是设计模式中比较简单的一个模式——单例模式(因为这里只牵涉到一个类) 二、单例模式的介绍 说到单例模式,大家第一

【2024 版】最新 kali linux 入门及常用简单工具介绍(非常详细)

一、介绍 kali Linux Kali Linux 是一个基于 Debian 的 Linux 发行版,主要用于数字取证和渗透测试。它预装了大量的安全审计和渗透测试工具,被广泛应用于网络安全领域。 (一)特点 工具丰富:集成了数百种用于渗透测试、漏洞评估、密码破解等方面的工具。开源免费:任何人都可以免费下载和使用,并且可以根据自己的需求进行定制。安全性高:经过严格的安全测试和更新,确保系

双头BFS

牛客月赛100 D题,过了80%数据,调了一下午。。。烦死了。。。 还是没调试出来,别人的代码用5维的距离的更新有滞后性,要在遍历之前要去重。。。 #include<bits/stdc++.h>using namespace std;const int N=2e3+10;char g[N][N];int dis[N][N],d1[N][N];int n,m,sx,sy;int dx

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历,在uva上找了个题敲了出来,感觉还不错,最近敲代码挺有手感的,希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in

【CF】D. Arthur and Walls(BFS + 贪心)

D题 解题思路就是每次检查2X2的方格里是否只有一个‘*’,如果有的话这个*就需要变成‘.’,利用BFS进行遍历,入队的要求是这个点为. 一开始将所有的'.'全部加入队列,如果碰到一个'*'变成'.'就入队,判断的时候从4个方向就行判断 题目链接:http://codeforces.com/contest/525/problem/D #include<cstdio>#include<