時間：2008 年 5 月 16 日（震後第 4 天）
地點：汶川縣牛腦寨
人物：羌族老奶奶
牛腦寨是一個 600 多人的羌族寨子，震後幾天，這裡仍常聽到隆隆聲響——對面山上石頭不斷滑落。完成搶修移動基站任務後，我拿起相機記錄受災情況。突然，視線中出現一位羌族老人，讓我無比震驚：那是極陡的坡，佝僂著腰的老人是如何艱難爬上來的？她上來做什麼？
老人身後是極陡的坡，僅有一隻眼睛有微弱視力，望著滿地廢墟徘徊良久。家在哪裡？她拼盡微弱視力尋找。曾經的家就旁邊，但滿目廢墟已讓她辨識不出。她舉目遠眺，期盼看到家的一點痕跡。原來家就在旁邊，左手抓住一塊房檐，勉強站穩。地震過了三天，這是她第一次回到曾經的家。
一個倒塌的櫃子，裡面裝著一絲希望。老人費力搬開覆蓋在櫃子上的薪柴，找到一把木匠用的刨子，老淚縱橫——或許有哪位逝去的親人是木匠。睹物思人，逝者已矣。
繼續尋找，一把散碎的掛麵映入眼簾。她顫顫巍巍撈起鋪滿灰塵的掛麵，再次流淚……看著她仔細把掛麵放進胸前圍裙，我驟然明白：這是老人在外援抵達前賴以生存的口糧。若非交通中斷、救援無法進入，80 多歲的老人豈會拖著軀體、強忍失去親人的痛苦，重返這奪走親人生命的廢墟，尋覓這點點掛麵？老人是真餓了……
老人佝僂著腰，低聲喃喃：「你們走了，我可怎麼活？」拿著對我們城市人微不足道的掛麵，遠去了……
補充：拍完這組照片後才知，5 月 14 日軍用運輸機首次向汶川空投物資就降落在牛腦寨，受災村民沒有佔為己有，而是汗流浹背走了兩小時背到山下縣城交給政府。
對於倖存災民，最迫切的是溫飽問題。救災部隊一邊搶通交通，一邊組織採購糧食。假設撥付一定救災經費去市場採購散裝大米。市場有 m 種大米，各自單價與重量已知，為滿足更多災民需求，最多能採購多少重量的大米？
首先一個正整數 C，表示測試案例數。
每組案例第一行兩整數 n、m（0<n≤1000, 0<m≤1000），分別為經費金額與大米種類數。
接下來 m 行，每行兩整數 p、h（1≤p≤25, 1≤h≤100），代表單價與該大米重量。
對每組測試數據，輸出能購買的最大大米重量（假設經費買不光所有大米），保留兩位小數，每實例佔一行。
1 7 2 3 3 4 4
2.33
經典分數背包問題。為在固定經費下獲得最大重量，應優先購買單位價格最低（即性價比最高）的大米。按單價 p 從小到大排序，依次購買：若經費足夠買下該種大米全部庫存，則全買並扣除費用；否則用剩餘經費盡可能多買該大米（可買部分），然後結束。
時間複雜度 O(m log m)，主要來自排序。
#include <cstdio>
#include <algorithm>
using namespace std;
struct Rice {
int price, weight;
} r[1010];
bool cmp(const Rice &a, const Rice &b) {
return a.price < b.price; // 單價升序
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
scanf("%d%d", &r[i].price, &r[i].weight);
sort(r, r + m, cmp);
double totalWeight = 0;
for (int i = 0; i < m && n > 0; i++) {
int costAll = r[i].price * r[i].weight;
if (costAll <= n) {
n -= costAll;
totalWeight += r[i].weight;
} else {
totalWeight += (double)n / r[i].price;
n = 0;
}
}
printf("%.2f\n", totalWeight);
}
return 0;
}
