题目描述
小王手里有点闲钱，想着做点卖水果的小买卖，给出两个数组m、n，用m[i]表示第i个水果的成本价，n[i]表示第i个水果能卖出的价钱，假如现在有本钱k元，试问最后最多能赚多少钱？
说明：
1.每种水果只能买一次，只能卖一次；
2.数组m,n大小不超过50；
3.数组元素为正整数，不超过1000。
输入描述
1.数组m, n;
2.本钱k
备注：
1.首行输入逗号分隔的数组m的元素值
2.第二行输入逗号分隔数字n的元素值
3.第三行输入本钱
输出描述
最多能赚多少钱。
示例1
输入
4,2,6,4
5,3,8,7
15
输出
22
说明
样例计算过程：
先买前3种水果，全部卖出，再买第4种水果，再卖出，最后本金变为22。
（感觉这个说明解释不正确……不是正确的解题思路……）
1.思考
- 先计算每种水果的平均利润，即收益/本金，并按照从大到小排序，这里使用pair<int, double>来将利润和水果index进行联系；
- 再按照利润从大到小来买水果，若本金足够则买入，否则买下一个便宜的，并将已经买过的水果用visit标记；
- 直到所有水果都买过，或者本金不足以支撑买最便宜的水果为止。
2.知识点
- 买入和卖出的价格不一定是个位数，这个string和int的转换过程中要注意；
- 在排序过程中将价格和最初的pair进行绑定，可以使用pair，及定义一个vector<pair<int, double>>类型；
- 判断结束的方式是：再购买并卖出一轮之后的价格和上一轮一样，说明没有可以买入的水果。
3.实现
- 自己仿真代码如下；
- 还可参考该思路：https://blog.csdn.net/yaoqi_isee/article/details/89368337
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;
int Str2Num(string s){
int len = s.size();
int n = 0;
for (int i = 0; i < len; i++){
n = n * 10 + s[i] - '0';
}
return n;
}
void Apart(string str, vector<int>& num){
int pos, n, len;
string s;
while (!str.empty()){
len = str.size();
pos = str.find(',');
if (pos > 0){
s = str.substr(0, pos);
n = Str2Num(s);
num.push_back(n);
str = str.substr(pos + 1, len-pos-1);
}
else{
n = Str2Num(str);
num.push_back(n);
break;
}
}
}
bool comp(pair<int, double>& a, pair<int, double>& b){
return a.second > b.second;
}
int main(){
string inputm, inputn;
while (getline(cin, inputm)){
//Input
vector<int> m, n;
int lenin = inputm.size();
getline(cin, inputn);
int k;
cin >> k;
Apart(inputm, m);
Apart(inputn, n);
//Calculate average profit and sort it
int len = m.size();
vector<pair<int, double>> avr;
for (int i = 0; i < len; i++){
avr.push_back(make_pair(i, (n[i] - m[i]) / (1.0*m[i])));
}
sort(avr.begin(), avr.end(), comp);
//Buy and sell
vector<int> visit(len, 0), win;
int i, idx, klast=-1;
bool brk = false;
while (!avr.empty()){
i = 0;
while (i < len){
idx = avr[i].first;
if (visit[i]==0 && m[i] < k){
k -= m[i];
win.push_back(n[i]);
visit[i] = 1;
}
i++;
}
k += accumulate(win.begin(), win.end(), 0);
win.clear();
if (k == klast)
break;
klast = k;
}
cout << k << endl;
}
return 0;
}