非常可乐

题目描述

大家一定觉得运动以后喝可乐是一件很惬意的事情,但是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日

相关文章

  • 2023.5.5 面向对象程序设计实验报告

    实验项目名称:模板 一、实验目的 1、熟练掌握函数模板和类模板的定义格式。 2、熟练运用函数模板和类模板解决实际问题。 二、实验内容 1、复数类Complex有两个数据成员:a和b, 分别代表复数的实部和虚部,并有若干构造函数和一个重载-(减号,用于计算两个复数的距离)的成员函数。 要求设计一个函数模板 template < class T > …

    C++ 2023年5月5日
    00
  • 第三部分:Spdlog 日志库的实现原理

    Spdlog 是一个快速、异步的 C++ 日志库,被广泛应用于 C++ 项目中。在这篇文章中,我们将探讨 Spdlog 日志库的实现原理。 Spdlog 的结构 Spdlog 由五个主要组件构成:Loggers、Sinks、Formatters、Async Logger 和 Registry。每个组件都扮演着不同的角色,共同协作记录并输出日志消息。 Logg…

    C++ 2023年4月18日
    00
  • 红与黑

    有一个矩形房间,覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上,由此出发,可以移到四个相邻瓷砖之一,但他不能移动到红砖上,只能移动到黑砖上。编写一个程序,计算他通过重复上述移动所能经过的黑砖数(一开始站立的黑砖也要算)。 输入 开头行包含两个正整数W和H,W和H分别表示矩形房间的列数和行数,且都不超过20.每个数据集有H行,其中每行包含W…

    C 2023年4月24日
    00
  • Qt-FFmpeg开发-视频播放(5)

    音视频/FFmpeg #Qt Qt-FFmpeg开发-视频播放【软/硬解码 + OpenGL显示YUV/NV12】 目录 音视频/FFmpeg #Qt Qt-FFmpeg开发-视频播放【软/硬解码 + OpenGL显示YUV/NV12】 1、概述 2、实现效果 3、FFmpeg硬解码流程 4、优化av_hwframe_transfer_data()性能低问题…

    C++ 2023年4月17日
    00
  • 洛谷:P5716日份天数

    题目描述 输入年份和月份,输出这一年的这一月有多少天。需要考虑闰年。 输入格式 输入两个正整数,分别表示年份 \(y\) 和月数 \(m\),以空格隔开。 输出格式 输出一行一个正整数,表示这个月有多少天。 样例 #1 样例输入 #1 1926 8 样例输出 #1 31 样例输入 #2 2000 2 样例输出 #2 29 提示 数据保证 \(1583 \le…

    C++ 2023年4月24日
    00
  • day3 函数的定义和调用,练习编写简单的程序(记录1)

    一、函数的定义 可以分为以下两种: 1、函数声明和函数定义分离 这种方法将函数声明和函数定义分开,通常在头文件中先声明函数原型,然后在源文件中实现函数定义。 例如,头文件 example.h 中声明了一个函数 add: #ifndef EXAMPLE_H #define EXAMPLE_H int add(int a, int b); // 声明函数原型 #…

    C++ 2023年4月18日
    00
  • 【Visual Leak Detector】Release 模式下使用 VLD

    说明 使用 VLD 内存泄漏检测工具辅助开发时整理的学习笔记。本篇介绍如何在 Release 模式下使用 VLD。同系列文章目录可见 《内存泄漏检测工具》目录 目录 说明 1. 思路概述 2. 在 QT 中实践 1. 思路概述 要在 RELEASE 模式下使用 VLD,必须在包含头文件 vld.h 前预先定义 VLD_FORCE_ENABLE 宏(参考 VL…

    C++ 2023年4月17日
    00
  • XMake学习笔记(1):Windows(MSYS2)下MinGW-w64环境搭建和XMake安装

    以前写的C++基本都是C with STL,大多是面向过程的算法题,或者比较小的项目,然后经常报各种编译错误(对编译原理不熟),经常把人搞到崩溃,搞不懂构建、链接之类的东西。 现在开始记录一下XMake的学习笔记,记录一些学习过程中踩的坑,在这篇文章,你将学习到Windows下利用MSYS2进行Mingw-w64环境搭建和XMake安装,并用Xmake构建一…

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