4.19华为_机试算法share

第一题：服务器能耗统计

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int n, res, q[N];

int main()
{
    cin >> n;
    int MAX = 0, MIN = N;
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        q[a]++, q[b + 1]--;
        MAX = max(MAX, b);
        MIN = min(MIN, a);
    }
    for (int i = MIN; i <= MAX; i ++ ){
        q[i] += q[i - 1];
        if(!q[i]) res += 1;
        else if(q[i] == 1) res += 3;
        else res+= 4;
    }
    cout << res << endl;
    return 0;
}

第二题：树上逃离

#include <iostream>
#include <queue>
#include <cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m, k, p;
int b[N], h[N], e[N], ne[N], idx;
string path[N], res[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void bfs(){
    queue<int> q;
    q.push(0);
    path[0] = "0";
    while (!q.empty()){
        int x = q.front();
        q.pop();
        int idx = 0; //用来记录i节点的子节点是否到达叶子节点，如果是的话将结果集res从小到大排序后输出结果
        for(int i = h[x]; i != -1; i = ne[i]){
            int j = e[i];
            if(!b[j]){
                q.push(j);
                path[j] = (path[x] + "->" + to_string(j));
                if(h[j] == -1) {
                    idx = 1;
                    res[p++] = path[j];
                }
            }
        }
        if(idx){ 
            sort(res, res + p);
            cout << res[0] << endl;
            return;
        }   
    }
    cout << "NULL" << endl;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cin >> k;
    for(int i = 0; i < k; i++){
        int t;
        cin >> t;
        b[t] = 1;
    }
    bfs();
    return 0;
}