【題目鏈接】
ybt 1973 【16NOIP普及組】買鉛筆
洛谷 P1909 [NOIP 2016 普及組] 買鉛筆
【題目考點】
1. 簡單數學
2. 數組
3. 向上取整
<cmath>中有函數double ceil(double x)，求x向上取整的值。
如果求正整數 ? a b ? \lceil \frac{a}{b} \rceil ?ba??也可以使用公式 ? a b ? = ? a ? 1 b ? + 1 \lceil \frac{a}{b} \rceil = \lfloor \frac{a-1}{b} \rfloor +1 ?ba??=?ba?1??+1，原理見求正整數a和正整數b的商向上取整
【解題思路】
已知需要總筆數為 n n n，只買一種包裝，設一種包裝的單價為 x x x，筆的數量為 y y y，購買這種筆 m m m包，買到筆的數量為 y ? m y\cdot m y?m。
買到筆的數量必須大于等于需要的筆的數量，因此有不等式： y ? m ≥ n y\cdot m \ge n y?m≥n，即 m ≥ n y m \ge \frac{n}{y} m≥yn?
由于m是整數，所以m的最小值為 ? n y ? \lceil \frac{n}{y} \rceil ?yn??
購買這種包裝的筆的最少花銷為 x ? m = x ? n y ? x\cdot m = x\lceil \frac{n}{y} \rceil x?m=x?yn??
? n y ? \lceil \frac{n}{y} \rceil ?yn??在代碼中，可以使用<cmath>中的ceil函數求，寫為ceil((double)n/y)，注意n和y都是int類型變量，要想進行實數除法，需要將其中一個數字轉為浮點型量。
或者可以設函數實現公式 ? a b ? = ? a ? 1 b ? + 1 \lceil \frac{a}{b} \rceil = \lfloor \frac{a-1}{b} \rfloor +1 ?ba??=?ba?1??+1，來求 ? n y ? \lceil \frac{n}{y} \rceil ?yn??。
比較購買三種包裝的筆需要的最小花銷，三者中的最小值就是最終結果。
【題解代碼】
寫法1：實現divCeil函數( ? a b ? = ? a ? 1 b ? + 1 \lceil \frac{a}{b} \rceil = \lfloor \frac{a-1}{b} \rfloor +1 ?ba??=?ba?1??+1)
#include<bits/stdc++.h>
using namespace std;
int divCeil(int a, int b)//求a/b向上取整(a、b都是正整數)
{return (a-1)/b+1;
}
int main()
{int n, x[3], y[3], ans = 1e9;//ans:最終的最少花費cin >> n;for(int i = 0; i < 3; ++i)cin >> y[i] >> x[i];//x[i]：第i包裝的單價 y[i]：第i包裝中筆的數量for(int i = 0; i < 3; ++i)if(ans > divCeil(n, y[i])*x[i])ans = divCeil(n, y[i])*x[i];cout << ans << endl;return 0;
}
寫法2：使用ceil函數
#include<bits/stdc++.h>
using namespace std;
int main()
{int n, x[3], y[3], ans = 1e9;//ans:最終的最少花費cin >> n;for(int i = 0; i < 3; ++i)cin >> y[i] >> x[i];//x[i]：第i包裝的單價 y[i]：第i包裝中筆的數量for(int i = 0; i < 3; ++i)ans = min(ans, (int)ceil(double(n)/y[i])*x[i]);//注意：min函數中兩個參數類型必須一致 cout << ans << endl;return 0;
}
