微软8.19第三次笔试，附题目及题解

菜狗第一次做微软笔试，本来AK了美滋滋，交了之后发现自己第二题边界忘记判掉好难过。还剩一次机会，加油。考试结束之后整理下题解。

牛客编辑器排版太差了，凑合着看吧orz

// 第一题主要思路，的对x坐标贪心 O(nlog(n))
// 应该也可以直接修改原数组，但怕出问题copy
int solution(vector<int> &X, vector<int> &Y, int W) {
		vector<int> puddles = X;
    sort(puddles.begin(), puddles.end());
    
    int ans = 0, border = -1; // border为最后一次drive的右边界

    for(auto x : puddles){
        if(border < x){
            ans ++;
            border = x + W;
				}
    }
    return ans;
}

//o(n)
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>

string solution(string &S) {
    vector<int> cnts(10, 0);
    string lstr, ans;
//开个size = 10的数组记录下每位数出现的次数
    for(auto c : S)
        cnts[c - '0'] ++;

//首先构建回文串的左边lstr，构建有两个原则：
//  1.枚举所有数字，将数字出现的次数除二加到左子串
//  2.为了结果最大，从9到0枚举（0开头非法，要判掉，忘记了，😭）
    for(int i = 9; i >= 1; i --){
        int t = cnts[i] >> 1;          
        lstr += string(t, char('0' + i));
    }
		if(lstr.size() > 0) lstr += string(cnts[0], '0'); 

    ans += lstr;
//如果有数字出现次数为奇数，找到一个最大的放到中间
    for(int i = 9; i >= 0; i --){
        if(cnts[i] % 2){
            ans += char('0' + i);
            break;
        }
        if(i == 0 && cnts[i] && !lstr.size())
            ans += '0';
    }
//左子串逆序加到后面。
    reverse(lstr.begin(), lstr.end());
    ans += lstr;
    return ans;
}

第三题.拓扑排序，dfs也可以做.

p[i]记录每个点的乘客数目，初值为1；

d[N] 记录每个点的度，当度减为1时（意味着，所有应当经过该点的乘客已经到达该点），将所有人送到下个点，计算代价。

1.目的地的度数减1

2.费用为乘客数/5 向上取整，

为了加速，用数组模拟队列。

#include<iostream>
#include<cstring>
#include<algorithm>
const int N = 1e5 + 10, M = N * 2;
int h[N], e[M], ne[M], idx = 0; //邻接表辅助数组
int d[N], q[M], p[N];   //q为拓扑排序的队列
void add(int a, int b) //邻接表添加边
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int solution(vector<int> &A, vector<int> &B) {
    int n = A.size(), fee = 0;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i ++) p[i] = 1; //init（）

    for(int i = 0; i < n; i ++)
        add(A[i], B[i]), add(B[i], A[i]), d[A[i]] ++, d[B[i]] ++; //加边，同时统计每个点的度数；
    
    int hh = 0, tt = -1;    //队列下标

    for (int i = 1; i <= n; i ++ )    //遍历所有点，将所有叶节点入队
        if (d[i] == 1){
            q[ ++ tt] = i;
            }
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        if(t == 0) continue;        //判掉0号点
        fee += (p[t] + 4) / 5;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            p[j] += p[t];
            if (-- d[j] == 1)
                q[ ++ tt] = j;
        }
    }
    return fee;
}