【笔试题】百度+美团

2023-03-16 07:37| 来源: 网络整理| 查看: 265

发工资

链接：https://www.nowcoder.com/questionTerminal/e47cffeef25d43e3b16c11c9b28ac7e8 来源：牛客网

小度新聘请了一名员工牛牛, 每个月小度需要给牛牛至少发放m元工资(给牛牛发放的工资可以等于m元或者大于m元, 不能低于m)。小度有一些钞票资金, 一共有n种不同的面额, 对于面额为x_ix i 的钞票, 小度有y_iy i 张, 并且每一个钞票面额都能整除所有比它大的面额, 并且每一张钞票不能找零。小度想知道这部分资金最多能牛牛发放多少个月的工资?

示例1 输入 3 51 100 1 50 4 1 2 输出 4 说明注意钱不能找零,所以: 100能支付一个月工资 50+1，50+1能支付两个月工资 50+50能支付一个月工资即最多能支付四个月的工资。

贪心 #include #include using namespace std; struct money{ long long mon; int num; }; bool cmp(money a, money b){ return a.mon > b.mon; } int main() { int a; long long sum = 0, b; cin >> a >> b; money arr[a]; for(int i = 0; i if(arr[i].mon >= b){ sum += arr[i].num; arr[i].num = 0; }else break; } //开始车轮战，每一趟while发出一个月工资 while(true){ long long needToPay = b; //先从大面额开始涮一轮，在不超b的情况下，尽可能地拿大面额 for(int i = 0; i sum++; continue; } //注意是倒序：再从小面额开始补（此时所有面额都已大于needToPay） for(int i = a - 1; i >= 0; i--){ if(arr[i].num == 0) continue; arr[i].num--; needToPay -= arr[i].mon; sum++; break; } if(needToPay > 0) break; } cout return true; } for(int i =0; i//当前得满足剩余的火柴棍得数目 ret.push_back(v[i].first+'0'); bool res = backtrack(mt,v,ret,n-v[i].second);//当前字符以及对应得剩余火柴棍数 if(res) return true; ret.pop_back();//回溯 } } return false; } int main(){ map nums; nums[1]=2; nums[2]=5; nums[3]=5; nums[4]=4; nums[5]=5; nums[6]=6; nums[7]=3; nums[8]=7; nums[9]=6; int n,m,x; while(cin>>n>>m){ vector v; for(int i =0; ix,nums[x]});//数字以及对应的火柴棍的数量 } sort(v.begin(),v.end(),[](pair a, pair b){ if(a.second!=b.second){ return a.second return a>b;//确保数字从大到小排序，这样得到的就是最大得数字 }); cout scanf("%d %d", &e1, &e2); g[e1].insert(e2); g[e2].insert(e1); } int color[n + 1]; // 存储每个节点对应的颜色 for (int i = 1; i g[u].erase(p); for (int v : g[u]) { dfs(v, u); } }; dfs(1, -1); map cnts; // 记录当前遍历子树的颜色及颜色对应的次数 function dfs2 = [&](int u) { cnts[color[u]]++; for (int v : g[u]) { dfs2(v); } }; int q; cin >> q; while (q--) { // dfs枚举答案 cnts.clear(); int node; cin >> node; dfs2(node); int ma = 0, resColor = -1; for (auto [colorIdx, cnt] : cnts) { if (cnt > ma) { ma = cnt; resColor = colorIdx; } } cout

【本文地址】

【笔试题】百度+美团

【笔试题】百度+美团

今日新闻

推荐新闻