华为2016校园招聘上机笔试题——成绩查询和更新

最近倒回去看了一下去年的华为机考题，发现难度和今年的完全不是一个档次...第一题就有挺多坑的

题目如下：

嗯，看起来就是用C++实现一下数据库的查询和修改功能。一般来说脑海里想到的第一个算法就是对的了，感觉Q操作可以先排序，也可以直接找最大值。

想了想先排序吧，开个临时数组截出指定的一段然后排序完返回头部就好（降序排序）。

于是写出代码如下：

#include <iostream>
#include <memory.h>
#include <algorithm>
#include <cstdlib>
#include <cstdio>

using namespace std;

int cmp(int a, int b)
{
    return a >= b;
}

int main()
{
    int N,M;
    while(cin >> N >> M){
        int grade[N];
        char op;
        int b, e;
        memset(grade, 0, N*sizeof(int));
        //char op;
        //int b, e;
        for(int i = 0; i < N; i++){
            cin >> grade[i];
        }
        for(int j = 0; j < M; j++){
            cin >> op >> b >> e;
            if(op == 'Q'){
                int temp[e - b + 1];
                memset(temp, 0, (e-b+1)*sizeof(int));
                for(int k = 0; k < e - b + 1; k++){
                    temp[k] = grade[k + b - 1];
                }
                sort(temp, temp + e - b + 1, cmp);
                cout << temp[0] << endl;
            }
            else if(op == 'U'){
                grade[b - 1] = e;
            }
        }
    }
    return 0;
}

嗯，跑样例也没错，应该是对了，提交。结果：程序未能在规定时间内完成。

心想着难道是cout的锅？然后改成了printf，依旧不行。

仔细一想，排序的时间复杂度是O（nlogn），而直接查找最大值的时间复杂度是O（n），那还是直接查找最大值吧。

于是改成如下：

#include <iostream>
#include <memory.h>
#include <algorithm>
#include <cstdlib>
#include <cstdio>

using namespace std;

int Max(int* array, int begin, int end)
{
    int temp = array[begin - 1];
    for(int i = begin - 1; i < end; i++){
        if(array[i] >= temp){
            temp = array[i];
        }
    }
    return temp;
}

int main()
{
    int N,M;
    while(cin >> N >> M){
        int grade[N];
        char op;
        int b, e;
        memset(grade, 0, N*sizeof(int));
        for(int i = 0; i < N; i++){
            cin >> grade[i];
        }
        for(int j = 0; j < M; j++){
            cin >> op >> b >> e;
            if(op == 'Q'){
                printf("%d\n",Max(grade, b, e));
            }
            else if(op == 'U'){
                grade[b - 1] = e;
            }
        }
    }
    return 0;
}

这次总该没问题了吧，我再提交：未能通过全部测试样例。仔细一看，原来Q操作后面跟着的两个数字有可能是前大于后的....

行吧，再加几行：

#include <iostream>
#include <memory.h>
#include <algorithm>
#include <cstdlib>
#include <cstdio>

using namespace std;

int Max(int* array, int begin, int end)
{
    int temp = array[begin - 1];
    for(int i = begin - 1; i < end; i++){
        if(array[i] >= temp){
            temp = array[i];
        }
    }
    return temp;
}

int main()
{
    int N,M;
    while(cin >> N >> M){
        int grade[N];
        char op;
        int b, e;
        memset(grade, 0, N*sizeof(int));
        for(int i = 0; i < N; i++){
            cin >> grade[i];
        }
        for(int j = 0; j < M; j++){
            cin >> op >> b >> e;
            if(op == 'Q'){
                if(e < b){
                    swap(b, e);
                }
                printf("%d\n",Max(grade, b, e));
            }
            else if(op == 'U'){
                grade[b - 1] = e;
            }
        }
    }
    return 0;
}

再提交，终于通过。由此可见如果做题之前不深思熟虑，那么再简单的题都有可能踩坑_(:з)∠)_

（话说这个毛病到现在都还没完全改过来