小米编程题:一定数目的钱,钱花完买到的最少的商品数量
一个简单的思路：因为要把钱花完，买到最少数量的商品，那就从最贵的开始买。
1，先把商品价格排序，然后从end()往begin()循环；
2，每轮循环时，先把最高单价，用muchprice保存，再判断余数为0？为0就把商存到表示数量的num数组中，更新总数量res，并且break跳出循环，返回res，不为0就把商存到num数组中，更新res，余数就是还剩余的钱，判断余数是否比最小的单价还小，小的话就是钱没花完，且剩余的钱已经买不了任何商品了，就返回-1；
3，否则进行再次循环，判断剩余的钱是否比本轮循环的最高单价小，如果小的话，肯定是不能买到这个单价的商品的，那就直接continue，跳过本次循环，进行到下一轮循环的最高单价。
思路感觉比较简单。为什么只能通过一部分；是有遗漏的地方吗？
int solution(vector < int > prices, int budget) {
int res = 0;
int len = prices.size();
int muchprice = 0;
vector<int> num(len,0);
sort(prices.begin(),prices.end());
if (budget <= 0) {
return -1;
}
for (int i = len-1; i >= 0; i--) {
muchprice = prices[i];
if (budget<muchprice) {
continue;
}
if (0 == (budget % muchprice)) {
num[i] = (budget / muchprice);
res = res+num[i];
break;
}else {
num[i]=(budget / muchprice);
res = res + num[i];
budget = budget%muchprice;
if (budget<prices[0]) {
return -1;
}
}
}
return res;
} #笔试题目##小米##题解#
投递XMind等公司10个岗位 >
