首页 > 试题广场 >

发工资

[编程题]发工资
  • 热度指数：1215 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小度新聘请了一名员工牛牛, 每个月小度需要给牛牛至少发放m元工资(给牛牛发放的工资可以等于m元或者大于m元, 不能低于m)。
小度有一些钞票资金, 一共有n种不同的面额, 对于面额为x_i的钞票, 小度有y_i张, 并且每一个钞票面额都能整除所有比它大的面额, 并且每一张钞票不能找零。
小度想知道这部分资金最多能牛牛发放多少个月的工资?

输入描述:
包括n+1行,第一行包括两个正整数。
接下来的n行, 每行两个正整数, 即面额和该面额所拥有的钞票数量。


输出描述:
一个整数，表示最多能支付多少个月工资。
示例1

输入

3 51
100 1
50 4
1 2

输出

4

说明

注意钱不能找零,所以:
100能支付一个月工资
50+1，50+1能支付两个月工资
50+50能支付一个月工资
即最多能支付四个月的工资。
算法知识视频讲解
开通博客
头像 沉默归来
发表于 2021-12-14 22:44:22
贪心法，确保每次选的钱浪费最少即越接近m越好，其实就是在不能凑齐m的时候优先用小额的钱去补就可以了。 #include<cstdio> #include<iostream> #include<cstring>  #include<algorit 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 大厂算法岗必拿下
发表于 2021-09-23 00:57:06
贪心法，只过了6/10. 但基本思想应该是这样。 大的方面，钱数弄完为止 钱按照面额从大到小排序。 #include<bits/stdc++.h> using namespace std; int main(){ int n,x,y; long long m; 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 牛客830168147号
发表于 2022-04-18 20:45:41
#include<bits/stdc++.h> using namespace std; bool comp(vector<int> a, vector<int> b) {  &nbs 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

C++工程师 PHP工程师 百度 2020 Java工程师
上传者：小小
难度：
5条回答 4237浏览

热门推荐

通过挑战的用户

相关试题

发工资

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号