建设网站投标标书范本,手机如何制作app,iis网站访问权限,电子商务网站建设试题及答案发工资
链接#xff1a;https://www.nowcoder.com/questionTerminal/e47cffeef25d43e3b16c11c9b28ac7e8 来源#xff1a;牛客网
小度新聘请了一名员工牛牛, 每个月小度需要给牛牛至少发放m元工资(给牛牛发放的工资可以等于m元或者大于m元, 不能低于m)。 小度有一些钞票资金…发工资
链接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能支付一个月工资 501501能支付两个月工资 5050能支付一个月工资 即最多能支付四个月的工资。
贪心
#include bits/stdc.h
#include vector
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 a; i){cinarr[i].monarr[i].num;}sort(arr, arr a, cmp);//第一种情况把大于工资的花完先把大钱用完for(int i 0; i a; 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 a; i){if(arr[i].num 0) continue;//比如需要支付的工资是51现在的面额是20那么需要51 / 20 2张并且接下来需要支付的工资变成51 - 40 11long long needNum needToPay / arr[i].mon;needNum min(needNum, (long long)arr[i].num);arr[i].num - needNum;needToPay - needNum * arr[i].mon;}//刚好凑成了就结束这一趟if(needToPay 0){sum;continue;}//注意是倒序再从小面额开始补此时所有面额都已大于needToPayfor(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;}coutsumendl;
}
// 64 位输出请用 printf(%lld)摆火柴
牛牛给了小度n根火柴和m种数字(m只能是1到9)小度只能摆这m种数字小度想知道能摆出来最大的数的多少。
如图所示: 摆数字1,2,3,4,5,6,7,8,9 分别需要花费 2,5,5,4,5,6,3,7,6根火柴。 时间限制C/C 2秒其他语言4秒 空间限制C/C 256M其他语言512M 输入描述 第一行两个数n,m。 第二行m个数表示小度可以摆放的数。 输出描述 一行表示答案。 示例1 输入例子 20 4 3 7 8 4 输出例子 777773 例子说明 火柴得使用完
贪心回溯
一种比动规好理解的回溯解法 首先需要字典映射。 当遇到选择列表的时候可以考虑回溯。 注意先要按照题意排序按照排序偏贪心的基础上在进行回溯。 最后的结果记得在字母排序
#includebits/stdc.h
using namespace std;bool backtrack(mapint,int mt, vectorpairint,int v, string ret, int n ){//base caseif(n0){return true;}for(int i 0; i v.size();i){if(v[i].secondn){//当前得满足剩余的火柴棍得数目ret.push_back(v[i].first0);bool res backtrack(mt,v,ret,n-v[i].second);//当前字符以及对应得剩余火柴棍数if(res) return true;ret.pop_back();//回溯}}return false;
}int main(){mapint,int 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(cinnm){vectorpairint,int v;for(int i 0; i m;i){cinx;v.push_back({x,nums[x]});//数字以及对应的火柴棍的数量}sort(v.begin(),v.end(),[](pairint,int a, pairint,int b){if(a.second!b.second){return a.second b.second;//火柴棍少的放在前面}else{return a.firstb.first; //数字大的放前面}});string res;//回溯来找在满足排序条件下最终能组成得字符串backtrack(nums,v,res,n);//当前字符以及对应得剩余火柴棍数sort(res.begin(),res.end(),[](char a, char b){return ab;//确保数字从大到小排序这样得到的就是最大得数字});coutresendl;}return 0;
}神秘的苹果树
链接https://www.nowcoder.com/questionTerminal/3f060b099d604ec3875d8826a69a4561 来源牛客网
小团找到一颗有n个节点的苹果树以1号节点为根且每个节点都有一个苹果苹果都有一个颜色但是这棵树被施加了咒术这使得小团只能从某一个节点的子树中选取某一种颜色的拿。小团想要拿到数量最多的那种颜色的所有苹果请帮帮她。每次她会指定一个节点t如果小团只能从节点t的子树中选取某一种颜色的苹果选取什么颜色能拿到最多的苹果如果有多种颜色都可以拿同样多的苹果输出颜色编号最小的那个对应的编号。
节点x的子树定义为所有将x当作祖先的节点x也视为x的子树的一部分。
输入描述: 第一行一个正整数n表示这颗树上节点的个数。
接下来n-1行每行两个正整数xi,yi,表示树上第i条边连接的两个节点。
接下来一行n个正整数ci分别表示从1~n号节点上的苹果的颜色。
接下来一行一个正整数q,表示接下来有q次独立的询问。
接下来q行每行一个正整数t表示询问如果小团只能从节点t的子树中选取某一种颜色的苹果选取什么颜色能拿到最多的苹果如果有多种颜色都可以拿同样多的苹果输出颜色编号最小的那个对应的编号。
对于100%的数据n≤5000, 1≤xi,yi,t≤n, ci≤1000000000,q≤1000
输出描述: 输出q行每行一个整数表示答案。
示例1 输入 7 1 2 1 3 2 4 2 5 3 6 3 7 1 1 2 1 2 2 3 7 1 2 3 4 5 6 7 输出 1 1 2 1 2 2 3
dfs
#include iostream
#include vector
#include map
using namespace std;mapint, int process(vectorvectorint edges, vectorint color, vectorint dp, int fa, int curr){mapint, int mp;mp[color[curr]];for(auto c : edges[curr]){if(c fa)continue;mapint, int temp process(edges, color, dp, curr, c);for(auto it : temp){mp[it.first] it.second;}}int maxVal 0, colorId -1;for(auto it : mp){if(maxVal it.second){maxVal max(maxVal, it.second);colorId it.first;}}dp[curr] colorId;return mp;
}int main(){int n;cin n;vectorvectorint edges(n1);for(int i 0; i n-1; i){int x, y;cin x y;edges[x].push_back(y);edges[y].push_back(x);}vectorint color(n1);for(int i 1; i n; i){cin color[i];}vectorint dp(n1, 0);process(edges, color, dp, 0, 1);int q;cin q;while(q--){int t;cin t;cout dp[t] endl;}return 0;
}
