非常可乐

题目描述

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

输入

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

输出

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

样例输入

7 4 3
4 1 3
0 0 0

样例输出

NO
3

代码

(不得不说好难啊)

#include <bits/stdc++.h>
using namespace std;
int vis[105][105][105];
int v[3];//可乐瓶和两个杯子的容量
int s,n,m,flag;
struct node{
	int coke[3];//可乐瓶和两个杯子当前的量
	int s;//倒的次数
};
void bfs()
{
	int avg=v[0]/2;
	memset(vis,0,sizeof(vis));
	flag=0;
	queue<node> q;
	node temp;
	
	temp.coke[0]=v[0];
	temp.coke[1]=0;
	temp.coke[2]=0;
	temp.s=0;
	
	vis[v[0]][0][0]=1;
	q.push(temp);
	while(!q.empty())
	{
		temp=q.front();
		q.pop();
		if((temp.coke[0]==avg&&temp.coke[1]==avg)||(temp.coke[0]==avg&&temp.coke[2]==avg)||(temp.coke[1]==avg&&temp.coke[2]==avg))
		{
			cout << temp.s << endl;
			flag=1;
			break;
		}
		//i杯子中的可乐往j中倒
		for(int i=0;i<3;i++)
		{//6种方案:0➡1  0➡2 1➡0 1➡2 2➡0 2➡1
			for(int j=0;j<3;j++)
			{
				if(i==j) continue;//自己不能给自己倒
				node tmp=temp;
				
				int pour=min(tmp.coke[i],v[j]-tmp.coke[j]);//取杯子i中的剩余可乐和杯子j中的剩余容量最小值
				tmp.coke[j]+=pour;
				tmp.coke[i]-=pour;
				
				if(!vis[tmp.coke[0]][tmp.coke[1]][tmp.coke[2]])
				{
					vis[tmp.coke[0]][tmp.coke[1]][tmp.coke[2]]=1;
					tmp.s++;
					q.push(tmp);
				}
			}
		}
	}
	if(!flag) cout << "NO\n";
}
int main()
{
	while(cin >> v[0] >> v[1] >> v[2]&&(v[0]||v[1]||v[2]))
	{
		if(v[0]%2==1)
		{
			cout << "NO\n";
			continue;
		}
		bfs();
	}
	return 0;
}

原文链接:https://www.cnblogs.com/momotrace/p/very-cola.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:非常可乐 - Python技术站

(0)
上一篇 2023年4月27日
下一篇 2023年4月27日

相关文章

  • 【Visual Leak Detector】核心源码剖析(VLD 1.0)

    说明 使用 VLD 内存泄漏检测工具辅助开发时整理的学习笔记。本篇对 VLD 1.0 源码做内存泄漏检测的思路进行剖析。同系列文章目录可见 《内存泄漏检测工具》目录 目录 说明 1. 源码获取 2. 源码文件概览 3. 源码剖析 3.1 注册自定义 AllocHook 函数 3.2 存储调用堆栈信息 3.3 生成泄漏检测报告 4. 其他问题 4.1 如何区分…

    C++ 2023年4月27日
    00
  • 从0开始学习c++

    常量指针与指针常量 #include<iostream> using namespace std; int main() { int a = 10; int b = 20; // 常量指针与指针常量 // 1.常量指针 const修饰指针 指针的指向是可以修改的(指针变量中存的地址值可以修改) 指针指向的值不能改(不能通过解引用的形式修改地址中存…

    C++ 2023年4月24日
    00
  • 第一部分:介绍 Spdlog 日志库

    什么是 Spdlog 日志库 Spdlog 是一个 C++ 的日志库,它具有高效、易用、跨平台等特点。它可以写入到控制台、文件等输出目标,支持多种日志级别、多线程安全等功能,非常适合在 C++ 项目中使用。 Spdlog 日志库的历史和背景 Spdlog 日志库最初由 Gabi Melman 开发,它最初是为了解决 C++ 中的日志记录问题而创建的。在很长一…

    C++ 2023年4月18日
    00
  • C++冒泡排序简单讲解

    什么是冒泡排序 冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。(这段话引用自菜鸟教程) 冒泡排序的基本思想 重复地走访要…

    C++ 2023年4月19日
    00
  • 面试最常问的数组转树,树转数组 c++ web框架paozhu实现

    刚毕业同学,找工作常被问 二维数组转树,树转二维数组 需要支持无限层级实现,如果你了解这个语言那么实现起来还要一番思考 c++ web框架 paozhu使用 需要实现数据库表数据到前台菜单实现,就是这种功能 二维数组转树,树转二维数组 保存时候树二维数组,展示时候树树状。 这个技术难点在于无限递归,这个树程序基本原理 现在看看c++怎么实现的,无限递归,家肯…

    C++ 2023年4月25日
    00
  • luogu_P1040 [NOIP2003 提高组] 加分二叉树

    P1040 [NOIP2003 提高组] 加分二叉树 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题意:给你一颗中序遍历为1到n的二叉树,和每个节点的val。树的值=左子树的值×右子树的值+根的val,空树值为1,求整个树最大值和这个值树的前序遍历。 题解:区间dp。dp[l][r]表示最大值,root[l][r]表示最大值的根,枚举区…

    C++ 2023年4月27日
    00
  • 前缀和

    前缀和 一、介绍 前缀,顾名思义就是一个东西前面的点缀…(bushi 其实打比方来说就是:假如有一字符串ABCD,那么他的前缀就是A、AB、ABC、ABCD这四个从新从第一个字母一次往后开始拼接的字符串。当然这是字符串。但前缀和一般应用于数组,对于给定的数组a=[1,2,3,4],他的前 i 项和sum[i]就表示数组中a[0]~a[i]的和,具体为:s…

    C++ 2023年5月3日
    00
  • 【Visual Leak Detector】配置项 MaxDataDump

    说明 使用 VLD 内存泄漏检测工具辅助开发时整理的学习笔记。本篇介绍 VLD 配置文件中配置项 MaxDataDump 的使用方法。同系列文章目录可见 《内存泄漏检测工具》目录 目录 说明 1. 配置文件使用说明 2. 设置每个泄漏块数据显示的最大字节数 2.1 测试代码 2.2 MaxDataDump 为空时的输出 2.3 MaxDataDump = 0…

    C++ 2023年4月18日
    00
合作推广
合作推广
分享本页
返回顶部