首页 > 代码库 > 1023:坑爹的黑店
1023:坑爹的黑店
题目描述
今天小明去了一个风景如画的地方散心，但是自己带的饮料喝完了，小明口渴难耐，见不远处有家小商店，于是跑去买饮料。
小明：“我要买饮料！”
店主：“我们这里有三种饮料，矿泉水1.5元一瓶，可乐2元一瓶，橙汁3.5元一瓶。”
小明：“好的，给我一瓶矿泉水。”
说完他掏出一张N元的大钞递给店主。
店主：“我忘了提醒你了，我们这里没有找客人钱的习惯的，多的钱我们都当小费收了的，嘿嘿。”
小明：“......”
小明环顾四周，就这一家商店，况且实在太渴了，就决定在这买了。不过小明想，与其把钱当小费送给他还不如自己多买一点饮料，反正早晚都要喝，但是要尽量少让他赚小费。
现在小明希望你能帮他计算一下，最少他要给店主多少小费。
输入格式
输入数据的第一行是一个整数T(1<=T<=100)，代表测试数据的数量。然后是T行测试数据，每个测试数据只包含一个正整数N（1<=N<=10000），N代表小明手中钞票的面值，以分为单位。
注意：商店里只有题中描述的三种饮料。
输出
对于每组测试数据，请你输出小明最少要浪费多少钱给店主作为小费，以分为单位。
样例输入
2
900
250
样例输出
0
50
最初想到的算法，妥妥的出错了
1 #include <stdio.h> 2 int main(void) 3 { 4 int time; 5 int money; 6 int remain; 7 8 scanf("%d",&time); 9 while(time--)10 {11 scanf("%d",&money);12 remain=money%350;13 14 remain=remain%200;15 16 remain=remain%150;17 if(money<150)18 money=remain; 19 printf("%d\n",remain);20 }21 return 0;22 }
后来发现这种算法并不对，比如450=3*150，而在我的算法中，先用350去减，剩下100。
下面是参考的官方的代码，不太明白。
#include<stdio.h>int main(){ int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); if(n<150) printf("%d\n",n); else if(n<=200||n>=300) printf("%d\n",n%50); else printf("%d\n",n-200); } return 0;}
下面的是从CSDN看到的代码，容易理解。相当于150*x+200*y+350*z的多项式，x,y,z分别从最大值到0不断尝试，以获得最接近money的值。
附上链接：http://blog.csdn.net/u011470356/article/details/9412157
1 <span style="font-size:18px;">#include <iostream> 2 using namespace std; 3 int main() 4 { 5 int n; 6 cin>>n; 7 int m,i,j,k; 8 9 for(m=0;m<n;m++)10 {11 int max=0;12 int s;13 cin>>s;14 for(i=s/350;i>=0;i--)15 {16 for(j=(s-i*350)/200;j>=0;j--)17 {18 for(k=(s-i*350-j*200)/150;k>=0;k--)19 {20 int p=i*350+j*200+k*150;21 if(p>max)22 max=p;23 }24 }25 26 }27 cout<<s-max<<endl;28 29 30 }31 return 0;32 }</span>
1023:坑爹的黑店
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。