一共五道题，四道基础题，一道压轴题，每题各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的用例

最后一题是关于红黑树测算法，属于专业测试题。