关注
确实是 找钱问题,参考了下,感觉现在应该没问题,好像还不用排序。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n;
vector<int> v;
int money;
while (cin >> n)
{
v.push_back(n);
}
money = v[v.size() - 1];
v.pop_back();
//sort(v.begin(), v.end());
int length = v.size();
int *days = new int[money + 1];
int *value = new int[money + 1];
days[0] = 0;
for (int i = 1; i <= money; i++)
{
int min = i;
int used = 0;
for (int j = 0; j < length; j++)
{
if (i >=v[j])
{
if (days[i - v[j]] + 1 <= min && (i == v[j] || value[i - v[j]] != 0))
{
min = days[i - v[j]] + 1;
used = v[j];
}
}
}
days[i] = min;
value[i] = used;
}
if (value[money] == 0)
cout << -1 << endl;
else
cout << days[money] << endl;
//system("pause");
return 0;
}
查看原帖
点赞 评论
相关推荐
投递阿里云等公司10个岗位
点赞 评论 收藏
转发
点赞 评论 收藏
转发
牛客热帖
正在热议
# 和牛牛一起刷题打卡 #
5026次浏览 456人参与
# 机械制造薪资爆料 #
341762次浏览 4057人参与
# 牛客帮帮团来啦!有问必答 #
991972次浏览 15346人参与
# 通信硬件薪资爆料 #
242869次浏览 2286人参与
# 腾讯工作体验 #
147014次浏览 1410人参与
# 你觉得机械有必要实习吗 #
10392次浏览 143人参与
# 如何写一份好简历 #
301825次浏览 4333人参与
# 秋招开了,你想投哪些公司呢 #
130053次浏览 3393人参与
# 实习必须要去大厂吗? #
18408次浏览 265人参与
# 你的简历改到第几版了 #
323641次浏览 4865人参与
# 机械制造2024笔面经 #
410387次浏览 6057人参与
# 毕业租房也有小确幸 #
32603次浏览 1975人参与
# 2022毕业生求职现身说法 #
20762次浏览 313人参与
# 0offer互助地 #
53481次浏览 558人参与
# 晒一晒我的offer #
3657442次浏览 56984人参与
# 2022届毕业生现状 #
337670次浏览 4598人参与
# 为什么国企只招应届生 #
56332次浏览 411人参与
# 视觉/交互/设计岗位评价 #
3379次浏览 61人参与
# 产品人专业大盘点 #
15139次浏览 120人参与
# 浅聊一下我实习的辛苦费 #
93762次浏览 920人参与