1023:坑爹的黑店，1023黑店

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 >#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>

坑爹的黑店

現在狠心商販很多。小心
 

捷信？坑爹的黑店

現在狠心商販很多。小心