Problem

题目描述

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.

输入输出样例

输入样例#1：

4 1 7
3 2
2 2
8 1
4 3

输出样例#1：

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.

Solution

思路

这道题目我们可以先将所有的券使用,然后在针对每一个更有的反悔,然后将反悔的东西用钱买,这就是一个正确的贪心思路

Code

#include<bits/stdc++.h> #define re register #define ll long long using namespace std; struct node{ ll val,id; bool operator<(node b)const{ return val>b.val; } }; priority_queue<node>a,b; priority_queue<ll,vector<ll>,greater<ll> >d; bool vis[1000010]; ll n,k,m; ll p[1000010],c[1000010]; int main() { #ifndef ONLINE_JUGDE freopen("in.txt","r",stdin); #endif scanf("%lld%lld%lld",&n,&k,&m); for(re ll i=1;i<=n;i++){ scanf("%lld%lld",&p[i],&c[i]); a.push((node){p[i],i}); b.push((node){c[i],i}); } ll ans=0; for(re ll i=1;i<=k;i++)d.push(0LL); while(m>0 && ans<n){ while(vis[a.top().id])a.pop(); while(vis[b.top().id])b.pop(); if(b.top().val+d.top()<a.top().val){ node now=b.top();ll id=now.id; ll x=now.val+d.top(); if(m<x)break;m-=x; d.pop(); d.push(p[id]-c[id]); vis[id]=1; } else{ node now=a.top();ll id=now.id; ll x=now.val; if(m<x)break;m-=x; vis[id]=1; } ans++; } printf("%lld\n",ans); #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } //注意lg上要更改代码

转载于:https://www.cnblogs.com/cjgjh/p/9512478.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/97109111

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。