可過全部數據
1 #include <iostream>
2 #include<malloc.h>
3 #include<fstream>
4 using namespace std;
5 ifstream ifs;
6 ofstream ofs;
7
8
9 int coins[6];//各面值硬幣數
10 int count=0;//需要的最少硬幣數
11 int cost,c[6]={ 5, 10,20,50,100,200};//需支付數和硬幣面值,以分計算
12 bool finish = false;
13 void getData()
14 {
15 int flag = 0;
16 for(int i=0;i<6;i++)
17 {
18 ifs>>coins[i];
19 flag = flag | coins[i];
20
21 }
22 if(!flag)
23 {
24 finish = true;
25 return ;
26 }
27 double costt;
28 ifs>>costt;
29 cost=(int)(costt*100);//將輸入的錢轉為 分
30 }
31
32 int contains(int a)
33 {
34 for(int i=0;i<6;i++)
35 {
36 if(c[i]==a&&coins[i]>0)return i;
37 }
38 return -1;
39 }
40
41 int getBackMin(int k)
42 {
43 int count = 0;
44 for(int i = 5;i >=0;--i)
45 {
46 count += k /c[i];
47 k = k % c[i];
48 }
49 return count;
50 }
51
52 //檢查一個數的后面是否還有硬幣，如果沒有了,或者余下的硬幣的和小于要找的值。那么就只能用當前硬幣來計算了
53 int checkLast(int index,int co)
54 {
55 int sum = 0;
56 for(int i =index - 1;i >=0;--i )
57 {
58 sum += c[i] * coins[i];
59 }
60 if(co <= sum)
61 return 1;
62 else
63 return 0;
64 }
65
66 void getMinCount()
67 {
68 for(int i=5;i>=0;i--)
69 {
70 if(coins[i]>0)
71 { int *cc=(int *)malloc((i+1)*sizeof(int));
72 cc[0]=0;
73 for(int k=1;k<i+1;k++)
74 {
75 cc[k]=c[k-1];
76 }
77 for(int j=0;j<1+i;j++)
78 {
79
80 if(cost>=(c[i]-cc[j]))
81 {
82 if(coins[i]>=cost/(c[i]-cc[j]))
83 { count+=cost/(c[i]-cc[j])+1;
84
85 if(contains(c[i]-cc[j])!=-1)
86 {
87 count--;
88 coins[contains(c[i]-cc[j])]-=cost/(c[i]-cc[j]);
89 }
90 else coins[i]-=cost/(c[i]-cc[j]);
91 cost=cost%(c[i]-cc[j]);
92 if(contains(c[i])==-1)break;
93 }
94 else
95 {
96 count+=coins[i];
97 cost=cost-c[i]*coins[i];
98 coins[i]=0;
99 }
100
101
102 }
103
104 }
105 //剩下的錢不夠支付了
106 if(!checkLast(i,cost))
107 {
108 //檢查是否可以用當前的幣值來支付
109 int hasLest = cost / c[i] + 1;
110 if(hasLest <= coins[i])
111 {
112 count += hasLest;
113 count += getBackMin(c[i] * hasLest - cost);
114 cost = 0;
115 break;
116 }
117 else
118 break; ;
119 }
120 }
121
122 }
123
124 if(count==0||cost!=0){ofs<<"impossible"<<endl;}
125 else
126 {
127 ofs<<count<<endl;
128 }
129
130 }
131
132
133 int main()
134 {
135 ifs.open("input.txt");
136 ofs.open("output.txt");
137 while(!finish)
138 {
139 count=0;
140 getData();
141 if(finish)
142 break;
143 getMinCount();
144 }
145 ifs.close();
146 ofs.close();
147 return 0;
148 posted on 2012-04-19 15:38
崔佳星 閱讀(135)
評論(0) 編輯 收藏 引用