关注
贪心算法,AC83%:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
using namespace std;
bool SortByM1(const int &v1, const int &v2)
{
return v1 > v2;
}
//main
int main(){
vector<int> vecPrice;
int nMoney;
int nTemp;
int nCount = 0;
int nCurrentNumber = 0;
string strLine;
getline(cin, strLine);
stringstream iss(strLine);
for (int i; iss >> i; vecPrice.push_back(i));
nMoney = vecPrice.back();
vecPrice.pop_back();
//降序排列
sort(vecPrice.begin(), vecPrice.end(), SortByM1);
vector<int>::const_iterator iter =
vecPrice.begin();
for (; iter != vecPrice.end(); iter++){
nCurrentNumber = *iter;
while (nCurrentNumber<=nMoney) //贪心算法
{
nCount++;
nMoney -= nCurrentNumber;
}
if (nMoney==0)
{
break;
}
}
if (nCount==0||nMoney>0)
cout << "-1" << endl;
else
cout << nCount << endl;
}
查看原帖
点赞 评论
相关推荐
投递阿里巴巴等公司10个岗位
点赞 评论 收藏
分享
查看23道真题和解析
点赞 评论 收藏
分享
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
1251326次浏览 17971人参与
# 实习时,大家都怎么称呼自己的mentor? #
19619次浏览 234人参与
# OPPO开奖 #
48089次浏览 640人参与
# 和牛牛一起刷题打卡 #
34216次浏览 2379人参与
# 硬件人的简历怎么写 #
83307次浏览 869人参与
# 2022毕业生求职现身说法 #
26341次浏览 373人参与
# 不去互联网可以去金融科技 #
40811次浏览 451人参与
# 你最多能接受一周加班几个小时 #
5273次浏览 56人参与
# 你的简历改到第几版了 #
342920次浏览 5141人参与
# 2023届毁约公司名单 #
101794次浏览 451人参与
# 你觉得今年秋招难吗 #
341590次浏览 6078人参与
# 你觉得通信/硬件有必要实习吗? #
30080次浏览 521人参与
# 24秋招避雷总结 #
375735次浏览 4162人参与
# 来聊聊你目前的求职进展 #
223025次浏览 2807人参与
# 实习生应该准时下班吗 #
100471次浏览 755人参与
# 24届软开秋招面试经验大赏 #
1209360次浏览 18428人参与
# 现在还是0offer,延毕还是备考 #
423385次浏览 4936人参与
# 互联网公司爆料 #
44294次浏览 400人参与
# 软件开发笔面经 #
16464次浏览 428人参与
# 正在实习的你,有转正机会吗? #
124856次浏览 1199人参与
# 你的秋招进行到哪一步了 #
415386次浏览 6858人参与
# 牛客解忧铺 #
1385460次浏览 22243人参与