牛客编程巅峰赛S2第5场 - 青铜&白银&黄金 题解

T1.牛牛算数

按照题意模拟即可。

找中位数的话直接排序，判断n的奇偶性即可。

平均数则扫描一遍整个数组，求一遍和再除以总元素个数即可。

class Solution {
public:
    /**
     * 
     * @param arr int整型vector 
     * @return int整型
     */
    int Answerofjudge(vector<int>& arr) {
        int n = arr.size();
        int a[1000005];
        for(int i = 0 ; i < n ; i ++)
            a[i + 1] = arr[i];
        sort(a + 1 , a + 1 + n);
        double sum = 0;
        for(int i = 1 ; i <= n ; i ++)sum += a[i];
        double zhong ;
        if(n % 2 == 1)zhong = (double)(a[n / 2 + 1]);
        else zhong = (double)((a[n / 2] + a[n / 2 + 1]) / 2.0);
        if(zhong == sum / double(n))return 0;
        if(zhong < sum / double(n))return -1;
        return 1;
    }
};

T2怕npy的牛牛

可以考虑两种做法，一种是贪心，另外一种是二分答案。

我们发现这个题目求的最长不包含'n','p','y'三个字符的子串具有“单调性”

倘若b > a,不存在长度为a的子串满足条件，那么定然不会存在一个长度为b的子串满足条件。

判断一个子串是否同时含有'n','p','y'三个字符考虑使用前缀和维护即可。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回符合题意的最长的子串长度
     * @param x string字符串
     * @return int整型
     */
    int sum1[1000005],sum2[1000005],sum3[1000005];
    int len;
    bool check(int x)
    {
        if(x > len)return 0;
        bool flag = 0;
        for(int i = 0 ; i + x - 1 < len ; i ++)
        {
            int r = i + x - 1;
            if(sum1[r] - sum1[i - 1] == 0 || sum2[r] - sum2[i - 1] == 0|| sum3[r] - sum3[i - 1] == 0)
                flag = 1;
        }
        return flag;
    }
    int Maximumlength(string x) {
        len = x.length();
        int Ans = 0;
        for(int i = 0 ; i < len ; i ++)
        {
            sum1[i] = sum1[i - 1];
            sum2[i] = sum2[i - 1];
            sum3[i] = sum3[i - 1];
            if(x[i] == 'n')sum1[i] ++;
            if(x[i] == 'p')sum2[i] ++;
            if(x[i] == 'y')sum3[i] ++;
        }
        for(int i = log2(len) + 1; i >= 0 ; i --)
            if(check(Ans + (1 << i)) ==  1)Ans += (1 << i);
        return Ans;
    }
};

T3.牛牛的后缀表达式

按照常规的后缀表达式求值直接模拟即可。

经典题了，特别模板。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 给定一个后缀表达式，返回它的结果
     * @param str string字符串 
     * @return long长整型
     */
    long long solve(string str) {
        int len = str.length();
        long long Ans[1000005];
        long long now = 0,i = 0;
        for(int j = 0 ; j < len ; j ++)
        {
            char op = str[j];
            if(op >= '0'&&op <= '9') {now *= 10 , now += op - '0' ; continue;}
            if(op == '#'){
                Ans[++ i] = now;
                now = 0;
            }
            if(op == '+'){
                Ans[i - 1] = Ans[i - 1] + Ans[i];
                Ans[i] = 0;
                i--;
            }
            if(op == '-'){
                Ans[i - 1] = Ans[i - 1] - Ans[i];
                Ans[i] = 0;
                i --;
            }
            if(op == '*'){
                Ans[i - 1] = Ans[i-1] * Ans[i];
                Ans[i] = 0;
                i --;
            }
        }
        return Ans[1];
    }
};

代码是赛时代码，比较丑，就不要喷了......