广中路街道网站建设,网站开发技巧,小说推广赚钱平台哪个好,网站怎么做好 优帮云P3045 [USACO12FEB]牛券Cow Coupons 71通过248提交题目提供者洛谷OnlineJudge标签USACO2012云端难度提高/省选-时空限制1s / 128MB提交 讨论 题解 最新讨论更多讨论 86分求救题目描述 Farmer John needs new cows! There are N cows for sale (1 N 50,000), and … P3045 [USACO12FEB]牛券Cow Coupons 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头奶牛(1N50000)第i头奶牛价格为Pi(1Pi10^9)。FJ有K张优惠券使用优惠券购买第i头奶牛时价格会降为Ci(1CiPi)每头奶牛只能使用一次优惠券。FJ想知道花不超过M(1M10^14)的钱最多可以买多少奶牛 输入输出格式 输入格式 Line 1: Three space-separated integers: N, K, and M. Lines 2..N1: Line i1 contains two integers: P_i and C_i. 输出格式 Line 1: A single integer, the maximum number of cows FJ can afford. 输入输出样例 输入样例#14 1 7
3 2
2 2
8 1
4 3 输出样例#13 说明 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 functionalusing 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;
} 转载于:https://www.cnblogs.com/zbtrs/p/7071526.html
