问题描述

   大家知道，在ACM基地每次算法专题学习学习优秀的成员是有奖励的，现在ACM基地主席小杜得到了教练给的一笔钱要去购买奖品。为了激发大家的学习积极性，给更多的成员颁发奖品，小杜想购买尽可能多的奖品发给大家。购买之前，小杜还向ACM基地成员征集了下奖品需求的情况，只要大家要求购买的就一定会买回来。当然每个奖品都需要花费一定的费用，当小杜的钱不够时就不能购买了。   现在，已知小杜得到的钱以及每个奖品的价格，请问小杜最多能购买多少个奖品？
输入第一行为一个整数T，表示有T种购买方案。对于每组数据：第一行是三个整数n, m, k，分别表示可供购买的奖品个数，成员要求购买的奖品个数，小杜身上的钱数（1≤m≤n≤10000, 1≤k≤10^9)。第二行是n个整数，第i个整数xi表示第i个奖品的价格(1≤xi≤10^9)。第三行是m个整数pi，表示成员要求购买的第pi个奖品（1≤pi≤n）。如果小杜带的钱连成员要求的奖品都无法全部购买，请输出-1；否则，请输出小杜最多能购买的奖品数。每组输出占一行。
输入范例25 2 104 3 8 1 121 25 2 104 3 8 1 121 3输出范例3-1#include #include #include #include #include #include #include using namespace std; vector P; int main() { int t, n, m; int tmp; long long k; scanf("%d", &t); while (t--) { scanf("%d%d%lld", &n, &m, &k); for (int i = 1; i <= n; i++) {//所有可以买的商品 scanf("%I64d", &tmp); P.push_back(tmp); } long long sum = 0; for (int i = 0; i < m; i++) {//要求买的奖品 int t; scanf("%d", &t); sum += P[t-1]; P[t-1] = -1; } if (sum > k) {//不够钱 printf("-1 "); } else if (sum == k) {//刚好够 printf("%d ", m); } else {//还有钱，买买买 int cou = m; k -= sum; sort(P.begin(), P.end());//升序排序 for (int i = 0; i < n; i++) { if (P[i] != -1 && P[i] <= k) {//去掉已经购买的，买过的没货了，不能再买了 cou++; k -= P[i]; } if (k <= 0) break; } printf("%d ", cou); } P.clear(); } return 0; }