文章目录
  1. 1. HDU 1288 Hat’s Tea
    1. 1.0.1. 题目描述
    2. 1.0.2. 分析
    3. 1.0.3. 代码

引言:细节很重要。


HDU 1288 Hat’s Tea

题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=1288

Hat is a member of PG Studio. Hat codes a lot and so he often buys tea at tea vending machine. But the tea vending machine just eat coins and spit out tea, if you feed the machine more coins than the tea’s price and the machine will not spit out your change.
Your program will be given numbers and types of coins Hat has and the tea price. The tea vending machine accepts coins of values 1, 5, 10 RMB (Jiao). The program should output which coins Hat has to use paying the tea so that he uses as many coins as possible.

大意是,一行给出4个整数。

第一个数是茶的价格,后面三个数分别为你拥有的1角、5角、10角硬币的个数。

4个整数全0为结束。

请给出买这杯茶消耗硬币个数最多的组合,如果买不了输出“Hat cannot buy tea.”,买得了输出“T1 YiJiao, T2 WuJiao, and T3 ShiJiao”。

分析

首先观察,可以看出这三种硬币很有特点,一个10,一个5,一个1。

题目要求消耗硬币个数最多,那么先贪心,尽可能使用10,再尽可能使用5,剩下的看1够不够,如果不够用则输出“Hat cannot buy tea.” 假设现在打算花出去的1、5、10的个数分别为a、b、c。

到现在a、b、c的组合一定可以exactly表示这杯茶的价格了。

现在尽量:

  1. 用手里剩下的两个5去代替打算花出去的一个10
  2. 用手里剩下的五个1去代替打算花出去的一个5
  3. 用手里剩下的十个1去代替打算花出去的一个10
  4. 用手里剩下的五个1和一个5去代替打算花出去的一个10

进行1至4步可以得到新的a、b、c,比较a、b、c是否变化,变化则继续进行1至4步,否则结束并输出结果。

为什么a、b、c三个数会抖动?

当我用5个1去代替一个5的时候,b会减1,那么我手里剩余的5角硬币会增加1,如果本来就剩余了一个5角硬币,现在就剩余了2个5角硬币,我现在又可以用2个5角去代替打算花出去的一个10角了。

坑在哪里?

我在做这道题的时候遇到了两个问题,一是抖动,抖动可以根据小例子自己观察出来,但上述步骤4则是比较隐蔽的,想到了1->5,1->10,5->10,就是没想到(1,5)->10。

这道题让我对拍了很久,不容易。

这道题网上还有另解,应该是数论吧,感兴趣的可以去翻一翻。

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f

int a,b,c,d,n,m,l;

/*
1 5 10
b c d
n m l
*/

int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
while(~scanf("%d%d%d%d",&a,&b,&c,&d) && !(!a&&!b&&!c&&!d)){
if(a>b+c*5+d*10){
puts("Hat cannot buy tea.");
}else{
int t=a;
l=min(d,t/10);
t-=10*l;
m=min(c,t/5);
t-=5*m;
if(b<t){
puts("Hat cannot buy tea.");
continue;
}
n=t;
bool changed=true;
while(changed){
int an=n,am=m,al=l;
int inc=min((c-m)/2,l);
l-=inc;
m+=inc*2;
inc=min((b-n)/10,l);
l-=inc;
n+=inc*10;
inc=min((b-n)/5,m);
m-=inc;
n+=inc*5;
//还有可能是1jiao剩5个,5jiao剩1个
if(b-n>=5 && c-m>=1 && l>=1){
l-=1;
n+=5;
m+=1;
}
changed=(an!=n)||(am!=m)||(al!=l);
}
printf("%d YiJiao, %d WuJiao, and %d ShiJiao\n",n,m,l);
}
}
return 0;
}
文章目录
  1. 1. HDU 1288 Hat’s Tea
    1. 1.0.1. 题目描述
    2. 1.0.2. 分析
    3. 1.0.3. 代码