-
- 71通過
- 248提交
- 題目提供者洛谷OnlineJudge
- 標簽USACO2012云端
- 難度提高+/省選-
- 時空限制1s / 128MB
?提交??討論??題解??
最新討論更多討論
- 86分求救
題目描述
Farmer John needs new cows! There are N cows for sale (1 <= N <= 50,000), and FJ has to spend no more than his budget of M units of money (1 <= M <= 10^14). Cow i costs P_i money (1 <= P_i <= 10^9), but FJ has K coupons (1 <= K <= N), and when he uses a coupon on cow i, the cow costs C_i instead (1 <= C_i <= P_i). FJ can only use one coupon per cow, of course.
What is the maximum number of cows FJ can afford?
FJ準備買一些新奶牛，市場上有N頭奶牛(1<=N<=50000)，第i頭奶牛價格為Pi(1<=Pi<=10^9)。FJ有K張優惠券，使用優惠券購買第i頭奶牛時價格會降為Ci(1<=Ci<=Pi)，每頭奶牛只能使用一次優惠券。FJ想知道花不超過M(1<=M<=10^14)的錢最多可以買多少奶牛？
輸入輸出格式
輸入格式：?
-
Line 1: Three space-separated integers: N, K, and M.
- Lines 2..N+1: Line i+1 contains two integers: P_i and C_i.
?
輸出格式：?
- Line 1: A single integer, the maximum number of cows FJ can afford.
?
輸入輸出樣例
4 1 7 3 2 2 2 8 1 4 3
3
說明
FJ has 4 cows, 1 coupon, and a budget of 7.
FJ uses the coupon on cow 3 and buys cows 1, 2, and 3, for a total cost of 3 + 2 + 1 = 6.
分析：其實很容易發現這就是一道背包題，對于每頭牛我們都有用與不用優惠券兩種選擇，然而會發現，這個m不是一般的大，所以不能用dp.dp和貪心是差不多的，考慮到dp不行，試試貪心。因為我們的目標是要使買的牛最多，也就是花的錢最少，于是我當時想了一種貪心：我們可以取前k個用優惠券的價格（從小到大排序），然后和不排序的放在一起排序一下，然后遍歷求解.這樣的話有一個問題：我們已經假定前k個用優惠券的牛用優惠券，然而有時候不用優惠券比用優惠券要好，那就是用不用價格都相等的情況，所以我們不再取前k個，我們把每頭牛拆成2頭牛，一頭用優惠券，一頭不用，然后排序求解即可.
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <functional>using namespace std;int n, k,p[50010],c[50010],vis[50010],ans; long long m;struct node {int id, use, money; }e[100010];bool cmp(node a, node b) {if (a.money == b.money)return a.use < b.use;return a.money < b.money; }int main() {scanf("%d%d%lld", &n, &k, &m);for (int i = 1; i <= n; i++){scanf("%d%d", &p[i], &c[i]);e[i * 2 - 1].id = i;e[i * 2 - 1].use = 1;e[i * 2 - 1].money = c[i];e[i * 2].id = i;e[i * 2].use = 0;e[i * 2].money = p[i];}sort(e + 1, e + n * 2 + 1, cmp);for (int i = 1; i <= n * 2; i++){if (vis[e[i].id])continue;if (e[i].use && k <= 0)continue;if (m <= 0)break;if (m >= e[i].money){vis[e[i].id] = 1;ans++;m -= e[i].money;if (e[i].use)k--;}}printf("%d", ans);return 0; }
?
