【笔试题】百度+美团

发工资

链接：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 <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++){cin>>arr[i].mon>>arr[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;}//注意是倒序：再从小面额开始补（此时所有面额都已大于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<<sum<<endl;
}
// 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
例子说明：
火柴得使用完

贪心+回溯

一种比动规好理解的回溯解法
首先需要字典映射。
当遇到选择列表的时候，可以考虑回溯。
注意先要按照题意排序，按照排序（偏贪心）的基础上，在进行回溯。
最后的结果记得在字母排序

#include<bits/stdc++.h>
using namespace std;bool backtrack(map<int,int>& mt, vector<pair<int,int>> v, string& ret, int n  ){//base caseif(n==0){return true;}for(int i =0; i< v.size();i++){if(v[i].second<=n){//当前得满足剩余的火柴棍得数目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<int,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(cin>>n>>m){vector<pair<int,int>> v;for(int i =0; i< m;i++){cin>>x;v.push_back({x,nums[x]});//数字以及对应的火柴棍的数量}sort(v.begin(),v.end(),[](pair<int,int> a, pair<int,int> b){if(a.second!=b.second){return a.second< b.second;//火柴棍少的放在前面}else{return a.first>b.first; //数字大的放前面}});string res="";//回溯，来找在满足排序条件下最终能组成得字符串backtrack(nums,v,res,n);//当前字符以及对应得剩余火柴棍数sort(res.begin(),res.end(),[](char a, char b){return a>b;//确保数字从大到小排序，这样得到的就是最大得数字});cout<<res<<endl;}return 0;
}

神秘的苹果树

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

小团找到一颗有n个节点的苹果树，以1号节点为根，且每个节点都有一个苹果，苹果都有一个颜色，但是这棵树被施加了咒术，这使得小团只能从某一个节点的子树中选取某一种颜色的拿。小团想要拿到数量最多的那种颜色的所有苹果，请帮帮她。每次她会指定一个节点t，如果小团只能从节点t的子树中选取某一种颜色的苹果，选取什么颜色能拿到最多的苹果？如果有多种颜色都可以拿同样多的苹果，输出颜色编号最小的那个对应的编号。

节点x的子树定义为所有将x当作祖先的节点，x也视为x的子树的一部分。

输入描述:
第一行一个正整数n表示这颗树上节点的个数。

接下来n-1行，每行两个正整数x­­i,yi,表示树上第i条边连接的两个节点。

接下来一行n个正整数c­i，分别表示从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;map<int, int> process(vector<vector<int>>& edges, vector<int>& color, vector<int>& dp, int fa, int curr){map<int, int> mp;mp[color[curr]]++;for(auto c : edges[curr]){if(c == fa)continue;map<int, 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;vector<vector<int>> edges(n+1);for(int i = 0; i < n-1; i++){int x, y;cin >> x >> y;edges[x].push_back(y);edges[y].push_back(x);}vector<int> color(n+1);for(int i = 1; i <= n; i++){cin >> color[i];}vector<int> dp(n+1, 0);process(edges, color, dp, 0, 1);int q;cin >> q;while(q--){int t;cin >> t;cout << dp[t] << endl;}return 0;
}