题目描述
小王手里有点闲钱，想着做点卖水果的小买卖，给出两个数组m，n，用m[i]表示第i个水果的成本价，n[i]表示第i个水果能卖出的价钱，假如现在有本钱k元，试问最后最多能赚多少钱？说明：
- 每种水果只能买一次，只能卖一次；
- 数组m,n大小不超过50；
数组元素为正整数，不超过1000
输入描述
第一行 数组m
第二行数组n
第三行本钱k输出描述
整数，表示最多能赚多少钱
输入输出示例
序号 样例输入 样例输出 说明 1 4,2,6,4
5,3,8,7
1522 无
题目解析
最直接的想法是用贪婪算法，每次选择当前成本能够购买的、利润最大的水果，然后卖出去，继续选择更新之后成本能够购买的、利润最大的水果，然后卖出去。
C++源码
#include <bits/stdc++.h>
using namespace std;
int str2Num(string s) {
int len = s.length();
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) {
stringstream ss(str);
string part;
while (getline(ss, part, ',')) {
num.push_back(str2Num(part));
}
}
class Pair {
public:
int first;
double second;
Pair(int first, double second) {
this->first = first;
this->second = second;
}
int getFirst() {
return first;
}
double getSecond() {
return second;
}
};
bool cmp(const Pair& p1, const Pair& p2) {
return p1.second > p2.second;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
string sm, sn;
while (getline(cin, sm)) {
if (sm.empty()) {
break;
}
vector<int> m, n;
getline(cin, sn);
int k;
cin >> k;
apart(sm, m);
apart(sn, n);
int len = m.size();
vector<Pair> avr;
for (int i = 0; i < len; i++) {
avr.push_back(Pair(i, (n[i] - m[i]) / (1.0 * m[i])));
}
sort(avr.begin(), avr.end(), cmp);
vector<int> visit(len), win;
int i, idx, klast = -1;
bool brk = false;
while (!avr.empty()) {
i = 0;
while (i < len) {
idx = avr[i].first;
if (visit[idx] == 0 && m[idx] < k) {
k -= m[idx];
win.push_back(n[idx]);
visit[idx] = 1;
}
i++;
}
k += accumulate(win.begin(), win.end(), 0);
win.clear();
if (k == klast) {
break;
}
klast = k;
}
cout << k << "\n";
}
return 0;
}python源码
def s2Num(s):
n = 0
for i in range(len(s)):
n = n * 10 + ord(s[i]) - ord('0')
return n
def sStr(str, num):
lists = str.split(",")
for i in lists:
num.append(s2Num(i))
class Node:
def __init__(self, fir, sec):
self.fir = fir
self.sec = sec
def First(self):
return self.fir
def Second(self):
return self.sec
def fun():
while True:
try:
sm = input().strip()
if not sm:
break
m, n = [], []
sn = input().strip()
k = int(input().strip())
sStr(sm, m)
sStr(sn, n)
L = len(m)
numL = []
for i in range(L):
if m[i] != 0:
t = Node(i, (n[i] - m[i]) / (1.0 * m[i]))
numL.append(t)
numL.sort(key=Node.Second, reverse=True)
mark = [0] * L
tmp = []
i = 0
id = 0
kL = -1
while numL:
i = 0
while i < L:
id = numL[i].First()
if not mark[id] and m[id] < k:
k -= m[id]
tmp.append(n[id])
mark[id] = 1
i += 1
k += sum(tmp)
tmp.clear()
if k == kL:
kL = k
return k
except:
break
Java源码
import java.util.*;
import java.io.*;
public class Main {
public static int str2Num(String s) {
int len = s.length();
int n = 0;
for (int i = 0; i < len; i++) {
n = n * 10 + s.charAt(i) - '0';
}
return n;
}
public static void apart(String str, List<Integer> num) {
String[] parts = str.split(",");
for (String part : parts) {
num.add(str2Num(part));
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String sm, sn;
while ((sm = br.readLine()) != null) {
if (sm.isEmpty()) {
break;
}
List<Integer> m = new ArrayList<>(), n = new ArrayList<>();
sn = br.readLine();
int k = Integer.parseInt(br.readLine());
br.readLine();
apart(sm, m);
apart(sn, n);
int len = m.size();
List<Pair> avr = new ArrayList<>();
for (int i = 0; i < len; i++) {
avr.add(new Pair(i, (n.get(i) - m.get(i)) / (1.0 * m.get(i))));
}
avr.sort(Comparator.comparing(Pair::getSecond).reversed());
List<Integer> visit = new ArrayList<>(Collections.nCopies(len, 0));
List<Integer> win = new ArrayList<>();
int i, idx, klast = -1;
boolean brk = false;
while (!avr.isEmpty()) {
i = 0;
while (i < len) {
idx = avr.get(i).first;
if (visit.get(idx) == 0 && m.get(idx) < k) {
k -= m.get(idx);
win.add(n.get(idx));
visit.set(idx, 1);
}
i++;
}
k += win.stream().mapToInt(Integer::intValue).sum();
win.clear();
if (k == klast) {
break;
}
klast = k;
}
System.out.println(k);
}
}
static class Pair {
int first;
double second;
public Pair(int first, double second) {
this.first = first;
this.second = second;
}
public int getFirst() {
return first;
}
public double getSecond() {
return second;
}
}
}