阿里笔试 4.29 第一题分水果
/*
题目：n种口味的水果分给m个人，每个人只能选一种水果，每种水果可以分给多个人，每个人分得的水果数相等，
问每个人最多可以得到多少水果？
#阿里笔试2020##笔试题目##阿里巴巴#
题目：n种口味的水果分给m个人，每个人只能选一种水果，每种水果可以分给多个人，每个人分得的水果数相等，
问每个人最多可以得到多少水果？
*/
思路：由题意可知，每个人只能选择一种水果，因此我们需要让每个人从 n 种水果中随机选择一种苹果，每个人可以重复选择一种水果，
设置一个数组man[m]，man[i] 保存第 i 个人所选择的种类；每个人选择的种类好种类后，就将水果按照每个人的选择逐个的循环发放给每个人，为了确保
每个人分的水果相等，当某种水果发放完毕时停止，此时，该种水果原有的数量除以所选择该种水果的人数（不够除就取整），即为每个人的最大水果数。
每个人选择水果的种类的不同都可能会造成最后的结果不同，因此问题的关键就是找到每一种可能的水果种类选择方式，即求出每一种 man[n] ，我这里
采用 暴力搜索+回溯 的方式寻找，当每找到一种选择情况后就求出该种情况下每个人能得到的水果数，保存每一种情况下的最大值即为所求，这里用 max 来保存；
注：这里暴力搜索其实是一种树形结构的深度优先遍历，树形结构为 n 叉树，每一个子树表示每个人选择的水果种类，数的层数为 m ,即人数，第 k 层表示第 k 个
人在第 k - 1个人已经选择的情况下继续选择 n 种水果之一，直达每个人都选择完毕（k > = m，k从0开始）为止。
暴力搜索的方式比较费时，可以适当的加一些剪枝条件来加速。
我觉得我这种办法有些笨，如果有大佬有比较简便的方法求多多指教啊！
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int max_Find(vector<int> apple, vector<int> man){
int count = 0;
//开始发水果 while(1){
for(int i = 0; i < man.size(); i++){ //每个人按照选择的种类发放一个水果 if(apple[man[i]] == 0){ //某种水果分配完毕，结束分配
return count;
}
else{
apple[man[i]]--;
}
}
count++; //每分配一次每个人得到的水果个数加一
}
}
void dfs_Choice(vector<int> &apple, vector<int> &man, int k, int &max){
if(k >= man.size()){ //每个人都选择完毕
int tmp = max_Find(apple, man) + 1; //分配剩下的水果并求得当前选择下的每人的最大水果数，此前每人已经分配了一个水果 max = tmp > max ? tmp : max;
return;
}
//第 k 个人选择水果种类
for(int i = 0; i < apple.size(); i++){
if(apple[i] == 0){ //该种水果已经没有了，选择下一种
continue;
}
man[k] = i;//第n个人选第 i 种水果 apple[i]--;
dfs_Choice(apple, man, k+1, max); //第k+1个人选择水果种类并得到一个该类水果 apple[i]++; //回溯
man[k] = -1;
}
}
int main(){
int T = 1;
cin >> T; //循环次数
int n,m; //n种水果分给m个人
int count = 0;
vector<int> apple; //存放每一种水果的个数
vector<int> man; //存放每个人选择的水果种类
while(count < T){
cin >> n >> m;
int total = 0;
apple.assign(n,0);
man.assign(m,-1);
for(int i = 0; i < n; i++){
cin >> apple[i];
total += apple[i];
}
if(total < m) { //水果不够分,输出0
cout << 0 << endl;
continue;
}
int max = 0; //保存每个人能分配的最大水果数
dfs_Choice(apple, man, 0, max); //从第 0 个人开始选择水果种类
cout << max << endl;
count++;
}
return 0;
} #阿里笔试2020##笔试题目##阿里巴巴#
查看10道真题和解析
