前言

腾讯今晚的笔试出一些问题，人流量这么大，有时候出现这种状况也是非常正常的，大家平常心就好，当然因此以下代码正确性存疑，欢迎讨论

第一题

牛牛有一棵二叉树，该二叉树节点的权值为0/1. 牛牛给你这棵二叉树,想让你告诉他该二叉树从根节点到叶子节点的所有路径中,节点"权值1的个数"比权值0的个数"多1的路径有多少条呢。 返回路径数目。

示例1

// 输入
{1, 0, 0, 1, 0, #, 1}

// 输出
2

示例2

// 输入
{0, 1, 1, 0, 1, 1, 0}

// 输出
2

思路与代码：

题目比较简单，深度优先搜索，并记录权值为1的节点个数 one 和 权值为0的节点个数 zero，对叶子节点进行判断，ans += ((one - zero) == 1) ；

class Solution {
public:
    int ans = 0;
    int pathNumber(TreeNode* root) {
        helper(root, 0, 0);
        return ans;
    }
    void helper(TreeNode* root, int one, int zero) {
        if (!root) {
            return;
        }
        int d1 = root->val == 1, d2 = root->val == 0;
        one += d1, zero += d2;
        if (!root->left && !root->right) ans += ((one - zero) == 1);
        helper(root->left, one, zero);
        helper(root->right, one, zero);
    }
};

第二题

牛牛有—个长度为n的序列a，以及—个长度为n-1的序列b，序列b中的元素不重复。 对于这个序列a牛牛会先求出他的中位数，然后再根据序列b的顺序依次删除原序列a中对应下标的元素，即删除α[b[i]],0<=i<n -1. 每次删除完—个数后，牛牛会统计序列a中剩下的数的中位数是什么，若剩下的数为奇数牛牛会取中问数(排序后),若为偶数牛牛会取中间两个数的平均值(排序后)。 牛牛把每次的结果都记录下来了，但是他怕出错，给你初始的序列a和b，希望你能帮他验证一下。

输入描述：

第一行为一个t,表示有t组数据。 接下来有3×行,每组数据的第一行为n表示序列长度。第二行为n个整数，表示序列a的元素。 第三行为n-1个整数,表示序列b的元素。

输出描述：

输出为行,每行有n个整数,表示每组数据的答案,其中输出若是浮点数保留小数点后一位,否则按整数输出。

示例1：

// 输入
2
5
2 2 1 3 5
3 1 2 5
4
1 1 1 1 
1 2 3

// 输出
2 2.5 3 4 3
1 1 1 1

// 说明
第一组数据中,初始序列a的中位数为2,输出2。
第一次要删掉α[b[0]]=a[3]=1后,中位数变为2.5，输出2.5,序列变为[2,2,3,5]。
第二次删掉a[b[1]]一2后,中位数变为3,输出3,序列度为[2,3,5]
第三次删掉a[b[2]=2后,中位数变为4,输出4，序列变为[3,5]
第四次删掉a[b[3]]=5后,中位数变为3,输出3，序列为[3]。

思路与代码：

（本题存疑）使用multiset保存数组a的全部元素，同时保存中位数迭代器：

• 数组长度为奇数，it为中位数迭代器
• 数组长度为偶数，it为较大中位数迭代器

然后根据每次删除的元素和迭代器it指向元素的大小关系，分情况讨论，并移动中位数迭代器：

• 删除元素大
• 删除元素小
• 删除元素和迭代器it指向元素相等

还有一个需要注意的点是，输出格式，如果是整数则正常输出，否则保留1位小数；这里采用的方法是int截断后，判断差值是否大于0.1；

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t; cin >> t;
    for (int i = 0; i < t; ++i) {
        int n; cin >> n;
        vector<int> a(n), b(n - 1);
        vector<double> ans;
        for (int i = 0; i < n; ++i) cin >> a[i];
        for (int i = 0; i < n - 1; ++i) cin >> b[i];
        multiset<int> st(a.begin(), a.end());
        
        // test
        auto it = next(st.begin(), (n / 2));
        if (n & 1) ans.push_back(*it);
        else {
            double a = *it;
            it--;
            double b = *it;
            ++it;
            ans.push_back((a + b) / 2.0);
        }
        for (int e : b) {
            int sz = st.size();
            int de = a[e - 1];
            if (de > *it) {
                if (sz & 1) {
                    double a = *it;
                    auto tt = it--;
                    double b = *it;
                    ++it;
                    ans.push_back((a + b) / 2.0);
                } else {
                    it--;
                    ans.push_back(*it);
                }
            } else if (de < *it) {
                if (sz & 1) {
                    double a = *it;
                    ++it;
                    double b = *(it);
                    ans.push_back((a + b) / 2.0);
                } else {
                    ans.push_back(*it);
                }
            } else {
                if (sz & 1) {
                    --it;
                    double a = *it;
                    ++it; ++it;
                    double b = *it;
                    ans.push_back((a + b) / 2.0);
                } else {
                    it--;
                    ans.push_back(*it);
                }
            }
            auto iter = st.find(de);
            st.erase(iter);
        }
        for (auto e : ans) {
            int c = e;
            if (e - c > 0.1) printf("%.1f ", e);
            else printf("%d ", c);
        }
    }
}

第三题

牛牛有一个长度为n的数组a={a1, a2,..., an}，定义f(a)为数组α中每个元素出现次数的最大值,如:f({1,2,3,3})-2,f({1,1,1})=3. 现在牛牛最多可以删除k个数字,现在他想使删除若干数字之后的f(a)尽可能的小,删除a_i的代价是i,请你帮牛牛计算f(a)的最小值以及使f(a)达到最小值的最小代价。

输入描述：

第一行输入两个正整数n,k,表示数组α的长度和最多可以删除的数字的个数。 第二行输入n个由空格隔开的正整数a1,a2,.…., an表示数组a

$1<k<n<10^5,1<a_i<10^9$< p=""></k<n<10^5,1<a_i<10^9$<>

输出描述：

一行输出由空格隔开的两个正整数分别表示f(a)所能达到的最小值以及使f(a)达到最小值的最少代价。

示例1：

// 输入
5 2
1 1 1 2 2

// 输出
2 1

// 说明
只删除a1，花费的代价为1,f(a)=2是最小值,因此答案为21。

示例2：

// 输入
3 3
1 1 1

// 输出
0 6

// 说明
删除 a1, a2, a3,f(a)-0为最小值。

思路与代码：

f(a)越大，需要删除的数越小；f(a)越小，需要删除的数越多；因此f(a)和删除元素的个数是单调关系，因此可以使用 二分查找，找到最多删除k个数字达到的最小f(a)值。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, k; cin >> n >> k;
    vector<int> arr(n);
    unordered_map<int, int> mp;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        mp[arr[i]] += 1;
    }
    ll l = 1, r = n, ans = 0;
    while (l <= r) {
        ll mid = (l + r) / 2;
        ll cnt = 0;
        for (auto& p : mp) {
            int k = p->first, v = p->second;
            if (v > mid) {
                cnt += v - mid;
            }
        }
        if (cnt > k) r = mid - 1;
        else l = mid + 1;
    }
    ll t = r;
    for (auto& p : mp) {
        int k = p->first, v = p->second;
        if (v > t) {
            ll cc = (t + 1 + v) * (v - t) / 2;
            ans += cc;
        }
    }
    cout << t << " " << ans;
}

第四题

有n个怪物,第i个怪物的战斗力为a，初始时，牛牛的战斗力为0 牛牛要与这n个怪物战斗，设牛牛与第i个怪物战斗时牛牛的战斗力为 x,，则:

1. 若x<a,则牛牛触发被动技能"勇敢牛牛不怕困难""使得自己的战斗力提升至α;并战胜这个怪物,这会让牛牛的勇气值提升 ai-x.
2. 若x ≥a,则牛牛会直接战胜这个怪物,并且本次战斗结束后，牛牛的战斗力会降低至ai.

牛牛可以任意决定与怪物战斗的顺序，牛牛想知道打败完所有的n只怪物之后，牛牛累计提升的勇气值最大可能是多少。

输入描述：

第一行一个整数n(1<n <200000)。 第二行n个整数a1, a2,.., an()。

输出描述：

输出一个整数表示牛牛可以得到的最大勇气值。

示例1：

// 输入
2
1 2

// 输出
2

示例2：

// 输入
3
1 2 2

// 输出
3

// 说明
牛牛先和编号为2的怪物战斗,此时牛牛的战斗力为0,牛牛获得a2-0=2-0=2的勇气值,之后牛牛的战斗力变为2。
牛牛再和编号为1的怪物战斗,此时牛牛的战斗力为2,牛牛获得0的勇气值,之后牛牛的战斗力变为1。
牛牛最后和编号为3的怪物战斗,此时牛牛的战斗力为1,牛牛获得a3-1=2-1=1的勇气值,之后牛牛的战斗力变为2。
牛牛总共获得2＋1一3的勇气值。

思路：

（本题存疑）一个想法是：排序之后，优先和战斗力最大的怪物战斗，然后再和战斗力最小的怪物战斗，依次类推，得到最后答案；

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n; cin >> a;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];
    sort(arr.begin(), arr.end());
    ll ans = 0;
    int c = 0, l = 0, r = n - 1;
    while (l < r) {
        ans += arr[r] - c;
        --r;
        c = arr[l++];
    }
    cout << ans;
}

第五题

某网站注册时需要输入密码，密码只能包含前m个小写字母，牛牛已经想好了自己密码的长度和某些位置的具体字符,现在需要你帮他确定其他位置的字符使得这个密码的复杂度尽可能大。 设一个密码的长度为len，则这个密码的复杂度等于在前len-1个字符中有多少字符与它后一个字符不同。 例如,对于密码abcc来说,他的复杂度为2，因为第—个和第二个位置的字符不同,第二个和第三个位置的字符也不同,而第三个和第四个位置的字符相同。

输入描述：

第一行两个空格分隔的正整数n, m,代表牛牛的密码长度和只能使用前m个小写字母。 第二行一个长度为n只包含小写字母的字符串s,保证只含有前m个小写字母和?,?代表需要你来帮忙确定的字符。

输出描述：

一行一个正整数代表密码的最大复杂度。

示例1：

// 输入
9 26
niuniu???

// 输出
8

// 说明
一种可能的密码是niuniuabc。

示例2：

// 输入
5 1
?????

// 输出
0

// 说明
唯一可能的密码是aaaaa。

思路与代码：

复杂度的定义是：某个字符不等于它后一个字符的数目；那么贪心思想：如果m>1的话，可以保证?都是满足复杂度定义条件的，而m=1时，就只可以填字符‘a’；因此可以根据m的值判断最终的答案；

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m; cin >> n >> m;
    string s; cin >> s;
    int ans = 0, i;
    for (i = 1; i < n; ++i) {
        if (s[i] == '?') continue;
        ans += s[i - 1] != s[i];
    }
    if (s[0] == '?') {
        if (m == 1) cout << 0;
        else cout << n - 1;
    } else {
        if (m == 1) {
            ans = s[i - 1] == 'a' ans ? : ans + 1;
        } else {
            cout << ans + n - i;
        }
    }
}