一线城市做网站工资有多少,企业网站轮播图怎么做,网站建设中国十强,哪个网站做任务给东西正题
jzoj题目链接:https://jzoj.net/senior/#main/show/5461 题目大意
有n个物品#xff0c;m元#xff0c;k个打折券。 每个物品打折前pip_ipi元#xff0c;打折后qiq_iqi元#xff0c;求最多能买多少物品。 解题思路
用可撤回贪心。 先将p和q分开排序#xff0c…正题
jzoj题目链接:https://jzoj.net/senior/#main/show/5461 题目大意
有n个物品m元k个打折券。 每个物品打折前pip_ipi元打折后qiq_iqi元求最多能买多少物品。 解题思路
用可撤回贪心。 先将p和q分开排序然后前k个都用打折劵。之和我们考虑一个新的东西如果必须打折的话那么就相当于用pmini−qminip_{min\ i}-q_{min\ i}pmin i−qmin i元买一个打折卷所以我们用堆用最大的进行比较买不买打折券好 code
#includecstdio
#includealgorithm
#includequeue
#define N 100010
using namespace std;
struct node{long long w,num;
}q[N],p[N];
long long n,k,m,ans;
priority_queue int K;
bool f[N];
bool cmp(node x,node y)
{return x.wy.w;}
int main()
{scanf(%lld%lld%lld,n,k,m);for(long long i1;in;i){scanf(%lld%lld,p[i].w,q[i].w);p[i].numq[i].numi;}sort(p1,p1n,cmp);sort(q1,q1n,cmp);//分开排序long long j1;for(long long i1;in;i){if(k)//前k个全要{if(mq[i].w){m-q[i].w;f[q[i].num]true;K.push(q[i].w-p[q[i].num].w);ans;k--;}}else{while(f[j]jn)j;//走到没有用过的if(mmin(p[j].w,q[i].w-K.top()))//买的起{m-min(p[j].w,q[i].w-K.top());if(p[j].wq[i].w-K.top()){m-q[i].w-K.top();K.pop();K.push(q[i].w-p[q[i].num].w);//压入堆}else j;//下一个最小的ans;//多买一个}}}printf(%lld,ans);
}
