解题思路：贪心算法

1. 问题分析

我们需要帮助Lucy计算最少需要向多少个朋友借邮票，才能凑齐她需要的数量。关键点在于：

• 每个朋友能借出的邮票数量不同
• 要尽可能少地向朋友借款
• 如果所有朋友能借的邮票总和仍不足，则判定为不可能

2. 算法选择

使用贪心算法，因为：

• 需要最小化借款的朋友数量
• 优先向能借出更多邮票的朋友借款可以更快达到目标
• 这种局部最优选择能保证全局最优解

3. 解决步骤

1. 输入处理：

   • 读取测试用例数量
   • 对每个测试用例：
     • 读取需要借的邮票数S和朋友数F
     • 读取每个朋友能借的邮票数量

2. 排序处理：

   • 将朋友能借的邮票数量按从大到小排序
   • 这样我们可以优先考虑能借出更多邮票的朋友

3. 贪心选择：

   • 初始化累计邮票数sum和借款朋友数count为0
   • 从能借出最多邮票的朋友开始：
     • 累加邮票数量
     • 增加借款朋友数
     • 检查是否已达到或超过需要的数量

4. 结果判断：

   • 如果累计数≥S，输出借款朋友数
   • 否则输出"impossible"

4. 算法实现细节

sort(friends.begin(), friends.end(), greater<int>()); // 降序排序
int sum = 0, count = 0;
for(int i = 0; i < F; i++) {
    sum += friends[i];
    count++;
    if(sum >= S) break; // 达到需求立即终止
}

5. 复杂度分析

• 时间复杂度：O(F log F)
  • 排序操作占主导，为O(F log F)
  • 线性扫描为O(F)
• 空间复杂度：O(F)
  • 存储朋友能借的邮票数量

6. 边界情况处理

• S=0：不需要借，输出0
• F=0：没有朋友可借，直接"impossible"
• 所有朋友能借的邮票总和<S：输出"impossible"

7. 算法正确性证明

贪心算法在这里能保证最优解，因为：

1. 每次选择能借出最多邮票的朋友
2. 这样能最快达到目标数量
3. 确保借款的朋友数最少

8. 示例推演

以输入样例1的第一个测试用例为例：

100 6
13 17 42 9 23 57

• 排序后：57, 42, 23, 17, 13, 9
• 借前3个朋友：
  • 57 (sum=57, count=1)
  • 42 (sum=99, count=2)
  • 23 (sum=122, count=3) → 满足100
• 输出3

9. 优化空间

• 如果邮票总数已知且小于S，可提前判断"impossible"
• 使用更高效的排序算法（如堆排序）可能略微提升性能

标程

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(int a, int b) {
	return a > b;
}

void solve() {
	int scenarios;
	cin >> scenarios;
	
	for (int scenario = 1; scenario <= scenarios; ++scenario) {
		int S, F;
		cin >> S >> F;
		
		vector<int> friends;
		for (int i = 0; i < F; ++i) {
			int stamp;
			cin >> stamp;
			friends.push_back(stamp);
		}
		
		// 从大到小排序
		sort(friends.begin(), friends.end(), compare);
		
		int sum = 0;
		int count = 0;
		bool possible = false;
		
		for (int i = 0; i < F; ++i) {
			sum += friends[i];
			count++;
			if (sum >= S) {
				possible = true;
				break;
			}
		}
		
		cout << "Scenario #" << scenario << ":" << endl;
		if (possible) {
			cout << count << endl << endl;
		} else {
			cout << "impossible" << endl << endl;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	solve();
	
	return 0;
}