發(fā)工資

鏈接：https://www.nowcoder.com/questionTerminal/e47cffeef25d43e3b16c11c9b28ac7e8
來(lái)源：?？途W(wǎng)

小度新聘請(qǐng)了一名員工牛牛, 每個(gè)月小度需要給牛牛至少發(fā)放m元工資(給牛牛發(fā)放的工資可以等于m元或者大于m元, 不能低于m)。
小度有一些鈔票資金, 一共有n種不同的面額, 對(duì)于面額為x_ix
i
?
的鈔票, 小度有y_iy
i
?
張, 并且每一個(gè)鈔票面額都能整除所有比它大的面額, 并且每一張鈔票不能找零。
小度想知道這部分資金最多能牛牛發(fā)放多少個(gè)月的工資?

示例1
輸入
3 51
100 1
50 4
1 2
輸出
4
說(shuō)明
注意錢(qián)不能找零,所以:
100能支付一個(gè)月工資
50+1，50+1能支付兩個(gè)月工資
50+50能支付一個(gè)月工資
即最多能支付四個(gè)月的工資。

貪心

#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);//第一種情況把大于工資的花完，先把大錢(qián)用完for(int i = 0; i < a; i++){if(arr[i].mon >= b){sum += arr[i].num;arr[i].num = 0;}else break;}//開(kāi)始車(chē)輪戰(zhàn)，每一趟while發(fā)出一個(gè)月工資while(true){long long needToPay = b;//先從大面額開(kāi)始涮一輪，在不超b的情況下，盡可能地拿大面額for(int i = 0; i < a; i++){if(arr[i].num == 0) continue;//比如需要支付的工資是51，現(xiàn)在的面額是20，那么需要51 / 20 = 2張；并且接下來(lái)需要支付的工資變成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;}//剛好湊成了就結(jié)束這一趟if(needToPay <= 0){sum++;continue;}//注意是倒序：再?gòu)男∶骖~開(kāi)始補(bǔ)（此時(shí)所有面額都已大于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 位輸出請(qǐng)用 printf("%lld")

擺火柴

牛牛給了小度n根火柴和m種數(shù)字(m只能是1到9)，小度只能擺這m種數(shù)字，小度想知道能擺出來(lái)最大的數(shù)的多少。

如圖所示: 擺數(shù)字1,2,3,4,5,6,7,8,9 分別需要花費(fèi) 2,5,5,4,5,6,3,7,6根火柴。
時(shí)間限制：C/C++ 2秒，其他語(yǔ)言4秒
空間限制：C/C++ 256M，其他語(yǔ)言512M
輸入描述：
第一行兩個(gè)數(shù)n,m。
第二行m個(gè)數(shù)，表示小度可以擺放的數(shù)。
輸出描述：
一行表示答案。
示例1
輸入例子：
20 4
3 7 8 4
輸出例子：
777773
例子說(shuō)明：
火柴得使用完

貪心+回溯

一種比動(dòng)規(guī)好理解的回溯解法
首先需要字典映射。
當(dāng)遇到選擇列表的時(shí)候，可以考慮回溯。
注意先要按照題意排序，按照排序（偏貪心）的基礎(chǔ)上，在進(jìn)行回溯。
最后的結(jié)果記得在字母排序

#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){//當(dāng)前得滿足剩余的火柴棍得數(shù)目ret.push_back(v[i].first+'0');bool res = backtrack(mt,v,ret,n-v[i].second);//當(dāng)前字符以及對(duì)應(yīng)得剩余火柴棍數(shù)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]});//數(shù)字以及對(duì)應(yīng)的火柴棍的數(shù)量}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; //數(shù)字大的放前面}});string res="";//回溯，來(lái)找在滿足排序條件下最終能組成得字符串backtrack(nums,v,res,n);//當(dāng)前字符以及對(duì)應(yīng)得剩余火柴棍數(shù)sort(res.begin(),res.end(),[](char a, char b){return a>b;//確保數(shù)字從大到小排序，這樣得到的就是最大得數(shù)字});cout<<res<<endl;}return 0;
}

神秘的蘋(píng)果樹(shù)

鏈接：https://www.nowcoder.com/questionTerminal/3f060b099d604ec3875d8826a69a4561
來(lái)源：?？途W(wǎng)

小團(tuán)找到一顆有n個(gè)節(jié)點(diǎn)的蘋(píng)果樹(shù)，以1號(hào)節(jié)點(diǎn)為根，且每個(gè)節(jié)點(diǎn)都有一個(gè)蘋(píng)果，蘋(píng)果都有一個(gè)顏色，但是這棵樹(shù)被施加了咒術(shù)，這使得小團(tuán)只能從某一個(gè)節(jié)點(diǎn)的子樹(shù)中選取某一種顏色的拿。小團(tuán)想要拿到數(shù)量最多的那種顏色的所有蘋(píng)果，請(qǐng)幫幫她。每次她會(huì)指定一個(gè)節(jié)點(diǎn)t，如果小團(tuán)只能從節(jié)點(diǎn)t的子樹(shù)中選取某一種顏色的蘋(píng)果，選取什么顏色能拿到最多的蘋(píng)果？如果有多種顏色都可以拿同樣多的蘋(píng)果，輸出顏色編號(hào)最小的那個(gè)對(duì)應(yīng)的編號(hào)。

節(jié)點(diǎn)x的子樹(shù)定義為所有將x當(dāng)作祖先的節(jié)點(diǎn)，x也視為x的子樹(shù)的一部分。

輸入描述:
第一行一個(gè)正整數(shù)n表示這顆樹(shù)上節(jié)點(diǎn)的個(gè)數(shù)。

接下來(lái)n-1行，每行兩個(gè)正整數(shù)x--i,yi,表示樹(shù)上第i條邊連接的兩個(gè)節(jié)點(diǎn)。

接下來(lái)一行n個(gè)正整數(shù)c-i，分別表示從1~n號(hào)節(jié)點(diǎn)上的蘋(píng)果的顏色。

接下來(lái)一行一個(gè)正整數(shù)q,表示接下來(lái)有q次獨(dú)立的詢問(wèn)。

接下來(lái)q行，每行一個(gè)正整數(shù)t表示詢問(wèn)：如果小團(tuán)只能從節(jié)點(diǎn)t的子樹(shù)中選取某一種顏色的蘋(píng)果，選取什么顏色能拿到最多的蘋(píng)果？如果有多種顏色都可以拿同樣多的蘋(píng)果，輸出顏色編號(hào)最小的那個(gè)對(duì)應(yīng)的編號(hào)。

對(duì)于100%的數(shù)據(jù)n≤5000, 1≤xi,yi,t≤n, ci≤1000000000,q≤1000

輸出描述:
輸出q行，每行一個(gè)整數(shù)，表示答案。

示例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;
}