华为面试题 最多换几瓶汽水喝

缘起

1
2
题目:
汽水两元一瓶,4个盖子或者2个空瓶子可以换一瓶汽水喝.问10元钱最多可以喝多少瓶汽水?

分析

关键我们要弄清楚2个问题（它们是递归出口）

  1. 一个空瓶子可以换一瓶汽水并且还多出一个盖子，瓶子不会剩余.

    因为我们可以向老板借一个空瓶子，然后两个瓶子换一瓶汽水，喝完之后，将空瓶子还给老板，并且我们还多出了一个盖子.

  2. 两个盖子可以喝2瓶汽水. 并且没有瓶子和盖子剩余.

    因为我可以向老板借2个盖子，换一瓶汽水，喝完还老板一个盖子（还有一个盖子没还），然后我们手头只剩下一个空瓶子，然后转换为情形1，最终我们可以再喝一瓶汽水，并且多出一个盖子刚好还老板那个盖子.

其实本题就是状态转移而已.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "stdafx.h"
#include <algorithm>
using namespace std;

int foo(int bottle, int pod) // bottle是瓶子, pod是盖子个数
{
	if (!bottle && pod<=2) return pod<=1?0:2; // 如果没有瓶子 盖子数量<=2 
	if (bottle<=1&&!pod) return bottle; // 如果没有盖子, 但是有不超过1个的瓶子, 则返回瓶子数量
	if (bottle&&pod>=2) return max(foo(bottle-1, pod+1)+1, foo(bottle, pod-2)+2); // 如果既有瓶子,盖子数量又>=2, 则在两种策略中取大
	if (pod<=1) return foo(bottle-1, pod+1)+1; // 如果盖子数量<2, 则只能用瓶子换汽水喝
	if (!bottle) return foo(bottle, pod-2)+2; // 如果没有瓶子, 则只能用盖子换汽水喝
}

int main()
{
	puts("输入钱数");
	int money;
	scanf("%d",&money);
	money>>=1;
	printf("%d\n",money+ foo(money, money)); // 首先拿money买money/2瓶汽水喝. 则喝完之后, 我们手头多了money/2个瓶子 money/2个盖子. 于是foo就是拿着这些瓶子和盖子做文章
	return 0;
}