練習題
Q11661: Burger Time (漢堡時刻)
題目連結 : http://luckycat.kshs.kh.edu.tw/homework/q11661.htm
[想法]
- 遇到Z，也就是同時是藥局跟餐廳，那麼最短距離為0，可以直接結束，不用再計算
- 遇到R或D，把他們記錄下來，所以每次遇到R或D的時候比較是否跟之前紀錄的資料相同，如果不同就代表這是藥局與餐廳之間的距離
- 如果找到這段距離比上次找到的距離還短，就更新答案
[code]
#include <iostream>
using namespace std;
int main() {
int L; //資料長度
char road, state;
int position;
int distance; //藥局與餐廳的距離，也就是案答
while (cin >> L && L != 0) {
state = '.';
position = -1;
distance = 2000001;
for (int i = 0; i < L; i++) {
cin >> road;
//如果有藥局跟餐廳合併的店，距離直接為0
if (road == 'Z') distance = 0;
//遇到藥局或是餐廳
if (road != '.') {
// 代表R遇到D或是D遇到R
if (state != road && state != '.') {
//目前的位置與前一個(R或D)的距離有比目前的最短路徑還短嗎?
if (i - position < distance) {
distance = i - position; //將最短距離更新
}
}
state = road; //紀錄最新的藥局或是餐廳
position = i; //紀錄位置
}
}
cout << distance << endl;
}
return 0;
}
Q11369: Shopaholic (購物狂)
[想法]
- 3樣物品，最便宜的那一樣免費，那絕對是拿最貴的3樣物品先結帳
- 所以我們要先將價位由大排到小，依序挑出3樣物品中最便宜的那一樣來計算
[code]
#include <iostream>
#include <algorithm>
using namespace std;
//比較大的數字放前面
bool cmp(int a, int b) {
return a > b;
}
int main() {
int num;
cin >> num; //測資的組數
while (num--) {
int i, j, n, save = 0, tmp;
int p[20000] = {
0
};
cin >> n; //商品數量
for (i = 0; i < n; i++) {
cin >> p[i]; //每樣商品的價錢
}
sort(p, p + n, cmp);
//每三個商品一起結帳
for (i = 2; i < n; i += 3) {
save += p[i]; //取得三樣商品中最便宜的價錢
}
cout << save << endl; //省下錢的總數
}
return 0;
}
d418: 00993 - Product of digits
https://zerojudge.tw/ShowProblem?problemid=d418
http://luckycat.kshs.kh.edu.tw/homework/q993.htm
內容 ：
給你一個大於等於 0 的整數 N，請你你找到最小的自然數 Q ，使得在 Q 中所有數字（digit）的乘積等於 N 。 例如：N=10, 可以找到Q=25，因為 2*5=10
輸入說明：
輸入的第一列有一個整數代表共有多少組測試資料。 每組測試資料一列有1個整數 N（0 <= N <= 1000000000
輸出說明：
每組測試資料輸出一列，輸出自然數 Q ，如果 Q 不存在，請輸出 -1。
範例輸入：
5 <-代表要輸入5筆測資
1
10
123456789
216
26
範例輸出：
1
25 ← 輸入是10，所以輸出是25，因為 2*5=10
-1 ← 沒有任何數字的每個位數相乘會是 123456789
389
-1
解題提示
題目大意:
給出一個正整數， 要求找到一個自然數，使得該自然數的每一位的數字的乘積等於正整數。並且要求最小，不存在輸出-1.
解題思路：
我們只能2~9這些數字去因式分解N，1因為除下來還是不便，所以可以略過
假如說N=64，能滿足各個位數相乘會是64的自然數有88, 448, 484, 844, 4444等
那該如何取得88呢? 其實就是用最大的因數去除以64就對了，2~9中如果拿8去除的話，得到的因數「個數」會比用4除來的少。
以N=324為例，我們用9~2這些數字來除以，先用9不斷去除以324，每除盡一次就把9存到我們的答案(答案成宣告一個陣列)，發現324可以被9除兩次，所以答案終究存了2個9，這時的324被2個9整除後會變成4，接著我們依序用8~5去除以4都沒辦法整除，接著用4除以4，並把4也存到答案裡面，此時的答案目前為{9,9,4}，而N也被分解成N=1，這也就代表N已經被除盡，可以不用再拿2跟3來除以N。
{9, 9, 4}可以被拿來組成499 , 949, 994，但我們要的是499，那我們該怎麼做呢？其實就是最小的數字移到陣列最左邊，最大的放最右邊，用sort就可以解決了。
1是比較特殊的情況， 因為終止條件是n == 1和i < 2, 所以一開始就要處理掉1的情況，單獨考慮， 然後當因子全部分解完之後，n 仍然不等1，說明不能完全分解成2 ~9之間的因子，輸出-1.
#include <iostream>
#include <algorithm>
using namespace std;
const int Max = 40;
int num[Max] = {0};//記錄N的所有因數
int main () {
int n, N, cnt;
cin>>n;//n比測資
while (n--) {
cin>>N;
cnt = 0; //N是用cnt個個位數字相乘
if (N != 1) {
//拿 9~2 來做因式分解，因為N只允許用個位數字當因數
for (int i = 9; i > 1; i--) {
while (N % i == 0) {
num[cnt++] = i;
N = N / i;
}
//N已被分解完成，提早跳出
if (N == 1) break;
}
//陣列是由大到小，所以要轉成由小到大
sort(num, num + cnt);
if (N != 1){
//找不到
cout<<"-1"<<endl;
}
else {
//找到了
for (int i = 0; i < cnt; i++)
cout<<num[i];
cout<<endl;
}
}
else{
//如果N=1的話，特例處理
cout<<"1"<<endl;
}
}
return 0;
}
其他練習
- Q12694: Meeting Room Arrangement
- http://luckycat.kshs.kh.edu.tw/homework/q12694.htm