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;
}解后反思
看起来不太像贪心的贪心，从能买得起的商品开始买即可