华为OD题库刷题记录1（掌握的单词个数+手机APP防沉迷+找朋友+流浪地球）

掌握的单词个数
模拟。
注意问号匹配，要走两次判断，先判断非问号匹配情况，没有匹配成功再遍历一遍chars去找有没有没用过的问号可以匹配，不然可能出现可以匹配自身却匹配到问号的情况，导致问号被浪费了。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    string s[n];
    for(int i = 0; i < n; i ++) {
        cin >> s[i];
    }
    string chars;
    cin >> chars;
    int answer = 0;
    int bucket[505];
    for(int i = 0; i < n; i ++) {
        if(s[i].size() > chars.size()) continue;
        memset(bucket, 0, sizeof(bucket));
        //result-当前元素有没有匹配成功
        int result = 0;
        for(int j = 0; j < s[i].size(); j ++) {
            //flag-当前位有没有匹配成功
            int flag = 0;
            for(int k = 0; k < chars.size(); k ++) {
                if(chars[k] == s[i][j] && !bucket[k]) {
                    //已经用过了
                    bucket[k] = 1;
                    flag = 1;
                    break;
                } 
            }
            if(!flag) {
                //尝试去匹配问号
                for(int k = 0; k < chars.size(); k ++) {
                    if(chars[k] == '?' && !bucket[k]) {
                        bucket[k] = 1;
                        flag = 1;
                        break;
                    }
                }
            }
            //当前位没有匹配成功，已经失败，直接退出
            if(!flag) {
                result = 1;
                break;
            }
        }
        //result未被标记为1（失败），说明匹配成功
        if(!result) {
            answer ++;
        }
    }
    cout << answer << endl;
}

手机APP防沉迷系统
也是模拟。
太久没写题手有点生了，反应半天才想到可以用结构体存每行数据，然后sort+cmp排序，优先级高的排前面，优先级相等先开始的排前面。
结构体中用status记录当前app是不是注册成功，排完序之后要遍历一遍每个元素，判断status状态，后面选择的时候必须要选择status为有效的元素，否则会出现本来应该输出NA却错误输出其他值的情况，比如这样几个数据：

app1 3 09:00 11:00
app2 2 08:00 11:30
11:20

如果不判断status，程序会输出app2，其实app2和app1存在冲突，根本没有注册成功

#include<bits/stdc++.h>
using namespace std;
struct App{
    string name;
    int    priority;
    int    start;
    int    end;
    int    status;
};
bool cmp(const App &apa, const App &apb) {
    if (apa.priority != apb.priority) {
        return apa.priority > apb.priority;
    } else {
        return apa.start < apb.start;
    }
}
int check[4546];
int main(){
    int n;
    cin >> n;
    App ap[n];
    for(int i = 0; i < n; i ++) {
        cin >> ap[i].name >> ap[i].priority;
        string st, se;
        cin >> st >> se;

        //开始时间，单位为分
        ap[i].start = 0;
        ap[i].start += 60 * stoi(st.substr(0, 2));
        ap[i].start += stoi(st.substr(3, 2));

        //结束时间
        ap[i].end = 0;
        ap[i].end += 60 * stoi(se.substr(0, 2));
        ap[i].end += stoi(se.substr(3, 2));

        ap[i].status = 1;
    }

    sort(ap, ap + n, cmp);

    string time;
    cin >> time;
    int t = 0;
    t += 60 * stoi(time.substr(0, 2));
    t += stoi(time.substr(3, 2));

    for(int i = 1; i < n; i ++) {
        for(int j = 0; j < i; j ++) {
           //本身就无效的app不必被比较
           if(ap[j].status == 0) {
            continue;
           }
           //排除不重叠的情况
           if(ap[i].start >= ap[j].end || ap[i].end <= ap[j].start) {
            continue;
           } 
           
           //必然重叠，第i个app必定注册失败
           ap[i].status = 0;       
           break;
        }
    }
    
    //按优先级从高至低寻找
    for(int i = 0; i < n; i ++) {
        if (ap[i].start <= t && ap[i].end > t && ap[i].status == 1) {
            cout << ap[i].name << endl;
            return 0;
        }
    }

    cout << "NA";
}

找朋友
简单遍历下就行。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int height[n], answer[n];
    memset(answer, 0, sizeof(answer));
    for(int i = 0; i < n; i ++) {
        cin >> height[i];
    }
    for(int i = 0; i < n - 1; i ++) {
        for(int j = i + 1; j < n; j ++) {
            if (height[j] > height[i]) {
                answer[i] = j;
                break;
            }
        }
    }
    for(int i = 0; i < n; i ++) {
        cout << answer[i] << " ";
    }

}

流浪地球
还是模拟。
用一个start数组保存每个发动机发动的时间，从0时刻开始模拟全部发动机开启的整个过程。
最后注意下输出格式。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n, e;
    cin >> n >> e;
    /*
    start[i]  -发动机i开启时刻
    num       -当前有几个发动机开了
    */
    int start[n], num = 0;
    for(int i = 0; i < n; i ++) {
        start[i] = 1005;
    }
    for(int i = 0; i < e; i ++) {
        int a, b;
        cin >> a >> b;
        start[b] = a;
    }
    /*模拟发动机开启过程
    从时刻0开始，到发动机全部开启结束
    i-时刻
    j-发动机序号
    */
    for(int i = 0; num < n; i ++) {
        for(int j = 0; j < n; j ++) {
            //当前应该启动的发动机
            if(start[j] == i) {
                num ++;
                //尝试更新其相邻发动机的启动时间
                //是个环，注意相应处理
                int next = (j + 1) % n, prev = (j - 1 + n) % n;
                if(start[next] > i + 1) {
                    start[next] = i + 1;
                } 
                if(start[prev] > i + 1) {
                    start[prev] = i + 1;
                } 
            }
        }
    }

    //全部启动成功，找start最大的即可
    int maxn = -1;
    for(int i = 0; i < n; i ++) {
        if(maxn < start[i]) maxn  = start[i];
    }

    num = 0;
    int ans[n];
    memset(ans, -1, sizeof(ans));
    for(int i = 0; i < n; i ++) {
        if(start[i] == maxn) {
            ans[num ++] = i;
        }
    }
    cout << num << endl;
    for(int i = 0; i < num; i ++) {
        if(i == 0) {
            cout << ans[i];
        }
        else {
            cout << " " << ans[i];
        }
    }
    cout << endl;
}