NEFU-1607 QWQ和神秘商人

NEFU-1607 QWQ和神秘商人

/ 0评 / 1719次 / 0

Description

众所周知,QWQ热衷于星际探险和旅行,一天他来到了K星,在这里他遇到了一位神秘的商人,这位商人手中有n个宝物,每个宝物都有一定的价格和珍藏值。如果QWQ想从商人手中购买宝物,就只能花费宇宙中唯一的通货——永恒宝石,但是在K星上关于购买宝物有奇怪的规定: 购买者手中永恒宝石的数量必须大于或者等于想要购买宝物的价格; 每当完成一个交易,购买者手中永恒宝石的数量就会变成所购买的宝物的价格,不论购买者原来有多少个永恒宝石; 现在,QWQ手中有k个永恒宝石,如果他想换取最大的珍藏值,这个值是多少呢?

Input

每组输入有三行
第一行 宝物数量n,初始宝石数量k
第二行 每一个宝物的价格
第三行 每个宝物的珍藏值 1 <= n <= 100000
其余输入均不大于100

Output

输出最大的珍藏值

Accepted Code

#include <bits/stdc++.h>
using namespace std;
struct $
{
    int jg;
    int zcz;
};
$ good[100001];
bool comp($ a,$ b)
{
    if(a.jg==b.jg)
    return a.zcz>b.zcz;
    else
    {
        return a.jg>b.jg;
    }
}
int main()
{
    int n,k,sum=0;
    cin>>n>>k;
    for (int i = 0; i < n; i++)
    {
        cin>>good[i].jg;
    }
    for (int i = 0; i < n; i++)
    {
        cin>>good[i].zcz;
    }
    sort(good,good+n,comp);
    for (int i = 0; i < n; i++)
    {
        if(good[i].jg<=k)
        {
            k=good[i].jg;
            sum+=good[i].zcz;
        }
    }
    cout<<sum<<endl;
    return 0;
}

解后反思

看起来不太像贪心的贪心,从能买得起的商品开始买即可

发表回复

您的电子邮箱地址不会被公开。

你好 No.63970