美团2020后天开发岗笔试题
一共五道题，四道基础题，一道压轴题，每题各20分，一共100分，时间为120分钟。
第一题：
题目场景为计算所有顾客对一家店铺的‘星级’计算。
input：
第一行输入一个数 五个数，每个数中间用空格隔开（例如： 4 5 6 7 8 9）（1 ≤ x ≤ 20000）
output：
输出五个数的加权平均，权值依次为[1 ,2 ,3 ,4 ,5]，结果保留一位小数（例如5.784，要保留5.7，不要产生进位）
样例：
200 400 500 600 800
3.5
代码实现：
#include <iostream>
#include <math.h>
using namespace std;
int main(){
int N = 5;
int arr[5];
for(int i =0;i < N;i++)
cin>>arr[i];
int sum =0;
int counter =0;
for(int i =0;i < N;i++)
{
sum += arr[i]*(i+1);
counter += arr[i];
}
//对于不进位的计算，采用了floor函数，现将结果扩大10倍
float res = floor(1.0*sum/counter * 10)/10;
cout<<res<<endl;
return 0;
}测试结果：通过显示%73的用例
第二题：
优惠券使用问题，美团退出满x优惠y的活动，x不一定大于y，例如x =1 ，y =2，这种情况下，店家直接按照两元优惠商品，但是不会找钱给顾客，问题小明有若干优惠券，计算小明在尽可能多使用优惠券的情况下，购买商品的总的价格和实际支付的金额数。
input：
第一行输入一个N，表示小明拥有的优惠卷数；
接下面N行，每行输入两个数x、y，表示该优惠卷满x可以优惠y元。
output：
一行，输出两个数，第一个数为商品总的价格，第二个数为实际支付的金额数。
样例：
input：
4
2 8
4 9
1 2
6 10
output：
29 15
代码实现：
#include <iostream>
#define M 50000
using namespace std;
int main(){
int N ;
cin>>N;
int arr[M][2];
for(int i =0;i < N;i++)
{
cin>>arr[i][0];
cin>>arr[i][1];
}
int total =0,discount = 0;
for(int i =0;i < N;i++)
{
// cout<<arr[i][0]<<", "<<arr[i][1]<<endl;
total += max(arr[i][0],arr[i][1]);//选择x,y最大的作为实际购买商品的价格
discount += arr[i][1];
}
cout<<total<<" "<<total - discount<<endl;
return 0;
}测试结果：
AC
第三题：
路径规划问题，一个花店有很多订单用户，外卖小哥要从花店给顾客送花，外卖小哥可以一次取多束华花，问题求花店到所有顾客的所有路径和也即，
始终用数字1，表示花店，ui表示顾客位置(1,ui)表示花店到顾客的距离，同时也便是这两点存在一条路，和外卖小哥实际走的最短路径，外卖小哥每次的最短路径中不用每次送完花然后再返回花店，假设n个地方只有n-1路径，也即到一个地点只有提条路。
input：
第一行输入一个N，表示花店和顾客的总数（这点算是一个小小的陷阱吧）；接下来（N-1）行每行表示三个数，x、y、z分别表示地点i，地点j，z表示两个地点之间的距离。
output：
输出一行两个数，第一个数表示花店到所有顾客的所有路径，第二个数是外卖小哥实际走的最短路径。
样例：
input：
5
1 2 3
1 3 2
1 4 1
2 5 1
output：
10 10
结果分析：外卖小哥走的路线可以为：1-3-1-4-1-3-5，所以结果是10，应为1-3-5这条路径最长，所有一定要最后一定最后走，因为不用返回1了，其他需要返回，不是表示返回花店买花，二是表示要到其他店铺，必须通过1才能到达。
代码：
#include <iostream>
#define M 300
using namespace std;
int find2(int i,int arrdis[2][M],int markers[])
{
int res = 0;
while(arrdis[0][i]!=0)//arrdis[i] == 0表示访问到花店
{
res += arrdis[1][i];
if(markers[i]==0)//第一次访问
{
markers[i] = 1;
}
else if(markers[i]==1)//已经访问过
{
markers[i] = 2; //再次访问就删除，因为总是从后往前访问
}
// cout<<i<<" ";
i = arrdis[0][i];//继续向前访问
}
// cout<<endl;
return res;
}
int main(){
int N ;
cin>>N;
int arr[M][3];
for(int i =0;i < N-1;i++)
{
cin>>arr[i][0];
cin>>arr[i][1];
cin>>arr[i][2];
}
//dis，realdis分别表示花店到所有点的路径已经外卖小哥实际做的而路径
int dis = 0,readis = 0;
int arrdis[2][M]={0};//存储位置之间的关系和距离
for(int i =0;i < N;i++)
{
arrdis[0][ arr[i][1] ] = arr[i][0];
arrdis[1][ arr[i][1] ] = arr[i][2];
}
//求各个顾客到花店的路径和路径长度
int markers[M] ={0}; //0表示未访问，1表示保留，2表示重复删除
int path[M] = {0};//花店到各个顾客的距离
for(int i =2;i <= N;i++)
{
path[i] = find2(i,arrdis,markers);//顾客i到花店的路径长度
}
//将重复的路径删除，只保留花店到顾客中不重复的路径
// 计算外卖小哥的实际所有最短路径长度
int realdis = 0;
int maxValue = 0;//记录最长的路径
for(int i =2;i <= N;i++)
{
//cout<<markers[i]<<","<<path[i]<<endl;
dis += path[i];
if(markers[i]==1)
{
//每条路径都计算二倍 ，
//最后减去一倍路径作为外卖小哥的实际走的路程
realdis += path[i]*2;
if(path[i] > maxValue)
maxValue = path[i];
}
}
cout<<dis<<" "<<realdis-maxValue<<endl;
return 0;
}测试结果：
当时没有通过，后来补充的。
第四题：
场景
input：
output：
样例：
代码：
测试结果：
第四题：
场景
小明有一堆不面额的代金券，顺序打乱，例如2,1,1，2，1，如果相邻两个代金券相同，可以进行一次合并，2,2,2,1，合并一次可以得到一张无限期使用的1元券，求小明最多可以得到多少无限期的1元卷。
input：
第一行输入N（2≤N≤500），表示代金券的个数，第二行输入N个数，分别表示代金券的面额x(1xi≤1000)。
output：
输出一个整数,表示获得的代金券的个数。
样例：
input：
5
2 1 1 2 1
output：
2
结果解释：2 2 2 1，4 2 1，无法合并合并两次
Method1：暴力破解
最多有500张代金券，每张最大100，合并后最大的结果不超过50，000；写一个两层for循环，主轮对不同面试的代金券进行合并，每一轮只合并一代金券
代码：
#include <iostream>
#define M 500
using namespace std;
int main(){
int N ;
cin>>N;
int arr[M];
for(int i =0;i < N;i++)
{
cin>>arr[i];
}
int amount = N;//当前代金券的数量
int flag = true;//是否有可以合并的代金券
int t = 0;//奖励数
int temp[500];//存储合并后的结果
int res = 0;
for(int j =1;j < 50000&&amount > 1;j++ )
{
// flag = true;
// amount = t;
t = 0;
for(int i =0;i < amount-1; )
{
if(arr[i]==arr[i+1] &&arr[i]==j)
{
res++;
temp[t++] = arr[i]+arr[i+1];
i+=2;
// flag = true
}
else
{
temp[t++] = arr[i];
i++;
}
}
for(int i =0;i < t;i++)
{
arr[i] = temp[i];
}
amount = t;
}
cout<<res<<endl;
return 0;
}测试结果：通过%43的用例
最后一题是关于红黑树测算法，属于专业测试题。
我现在也只有一个保底
太难了