目錄
b138. NOIP2005 1.陶陶摘苹果
題目大意：先給你 10 顆蘋果的高度，再給你陶陶伸手能及的高度，問陶陶踩在 30 公分高的凳子上可以採到幾顆蘋果？
說明：
這題的測資很討厭，如果他先給你陶陶能及的高度，再給你 10 個蘋果的高度的話，那麼我們只要一個很簡單的迴圈就可以完成了：
int a, h, c=0, i;
cin >> h;
for (i=1; i<=10; i++) {
cin >> a;
c += (a <= h + 30);
}
cout << c << endl;
但是它卻先給你蘋果的高度，你得先把蘋果的高度全部輸入完後才能讀到陶陶的高度。當然你也可以很暴力地宣告 11 個變數把所給的數字全部輸入然後再算出可以摘到幾顆蘋果，如下：
int a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, h, c;
cin >> a1 >> a2 >> a3 >> a4 >> a5 >> a6 >> a7 >> a8 >> a9 >> a10;
cin >> h;
h += 30;
c = (a1<=h) + (a2<=h) + (a3<=h) + (a4<=h) + (a5<=h) +
(a6<=h) + (a7<=h) + (a8<=h) + (a9<=h) + (a10<=h);
cout << c << endl;
但是萬一題目是 100 個蘋果呢？甚至是 n 個蘋果呢？總得有個比較好的解決方式吧？
7.1 陣列
當我們用 int a; 宣告一個變數 a 時，這個變數同時只能儲存一個 32 位元的整數，當我們設定一個新的值給 a 時，原先在變數 a 內的值就會被覆蓋。但是如果我們的程式需要處理數以萬計的數字時，總不能定義幾萬個變數名稱來使用吧！為了這個目的，C++ 提供了「陣列」這個資料型態。
在 C++ 中，下列的程式碼代表我們宣告了一個可以儲存 10 個整數的陣列 a。
int a[10];
在這個陣列中，我們可以同時儲存 10 個整數，我們可以把 a 視為 10 個 int 的集合。為了方便存取這集合中的個別 int，C++ 將這 10 個整數依序編號為 0 到 9。當程式中要使用其中個別的 int 整數時，就必須要用「下標」運算子 [ ] 來指定它的編號。例如，我們要依序輸入 10 個蘋果的高度，我們可以這樣寫：
cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4] >> a[5] >> a[6] >> a[7] >> a[8] >> a[9];
也就是說，我們可以宣告一個 10 個 int 的陣列 a，然後用 a[0] 來代替原來的 a1、用 a[1] 代替原來的 a2、….。但是如果只是這樣替換而已反而會使程式碼變得更長，沒有任何好處。陣列的下標和字串的下標一樣，可以用變數來代入，如此一來，我們就可以用迴圈來簡化程式了。
int a[10], h, c=0, i;
for (i=0; i<10; i++) // 將蘋果高度輸入陣列
cin >> a[i];
cin >> h; // 輸入陶陶高度
for (i=0; i<10; i++) // 計算採得到幾顆蘋果
c += (a[i] <= h + 30); // c(ount) -- 計數
cout << c << endl;
你可能會覺得這個版本並沒有比之前「暴力版」短多少，那麼看看下面這題，暴力法就完全行不通了。
c067. Box of Bricks
題目大意：給你 n 疊立方塊的高度 hi，問最少要移動幾塊立方塊才能讓每疊都一樣高。
說明：
這題要先求出每疊立方塊的平均高度，然後把所有超出平均高度的部份加總就是答案了。
在求平均高度前，要先輸入每一疊的高度並加總。求出平均高度之後，又得回頭去和每疊的高度作比較。因此，這也是典型的陣列應用 – 我們得先把所有的高度輸入、加總，並存入陣列之中。求出平均高度之後，再回頭和陣列中所儲存的每疊高度一一作比較並把超出的部份加總。
這其中有一個問題：測試資料中會有幾疊立方塊得等程式開始執行並輸入 n 之後才會知道，那麼我們解題時到底要開多大的陣列呢？開太大會浪費記憶體，開太小程式會爆掉。還好，像這一類的題目通常會明確指定 n 的範圍，我們程式中的陣列大小必須能處理範圍內所有的可能狀況。以本題來說，題目在輸入說明中明確地說明 1 ≤ n ≤ 50，因此我們的陣列至少必需可以儲存 50 個整數。
//591 - Box of Bricks (by Snail)
#include <iostream>
using namespace std;
int main () {
int n, i, h[50], a, m, tc=1; // 陣列 h 要有 50 個元素
while (cin >> n, n) {
a = 0;
for (i=0; i<n; i++) {
cin >> h[i]; // 輸入高度
a += h[i]; // 並加總
}
a /= n; // 求平均高度
m = 0; // m(oves) -- 移動個數
for (i=0; i<n; i++)
m += max (0, h[i] - a); // 超出平均高度的個數
cout << "Set #" << tc++ << endl; // 依題意要求輸出
cout << "The minimum number of moves is" << m << ".\n\n";
}
}
b078. E. 白飯
題目大意：給你 n 個整數，問其中有幾個數小於平均值。
說明：上一題的類題，就自已試一下吧！
b026. H. PS3
題目大意：給定 n 個點的 x, y 座標，問哪兩點之間的距離最長。
說明：這題需要開兩個陣列，一個陣列用來存 x 座標，另一個陣列用來存 y 座標。
int x[3000], y[3000];
接下來輸入 n 個點的座標。
for (i=0; i<n; i++)
cin >> x[i] >> y[i];
由於它只是要求出點的編號，所以只要算出兩點之間距離平方就可以比大小，並不需要去開根號。
d2 = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
其中的 i 和 j 各需要一層的迴圈來處理。
b082. C. 國家寶藏
題目大意：給定 m 張骨牌，每張骨牌包含了這張骨牌的編號、所代表的字母、及下一張骨牌的編號，問所串連起來的骨牌所代表的文字。
說明：這題需要開兩個陣列，第一個陣列儲存每張骨牌所代表的字母，另一個陣列儲存下一張骨牌的編號。
b101. A. 收集凱蒂貓
b127. 會議中心（Room）
費氏數列
排列
d829. 146 - ID Codes
next_permutation
二維陣列
int a[3][3];
/*
* /----- a[0] -----\ /----- a[1] -----\ /----- a[2] -----\
* a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2] a[2][0] a[2][1] a[2][2]
*/
a[0] = { a[0][0], a[0][1], a[0][2] };
a[1] = { a[1][0], a[1][1], a[1][2] };
a[2] = { a[2][0], a[2][1], a[2][2] };