华为软件类笔试-嵌入式软件开发 11-8

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《软件开发笔试汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

3、手机芯片CPU任务调度

手机芯片的性能是有限的,因此手机芯片CPU的任务调度尤其重要。假设手机CPU所有需要处理的任务是一个完全二叉树,且每个任务的优先级不同，优先级按从高到低层级排列,相同一层的节点优先级一样。CPU需要优先处理优先级高的任务,同一层任务没有处理完前不能处理下一层的任务。CPU依次处理单个任务,每个节点值代表执行任务需要的时间。

给定一个有限的时间,及任务的完全二叉树,请编写一个函数,计算CPU最高利用率下可执行的任务个数,即优先保证CPU连续运行时间最长前提下,运行的任务最多。

解答要求

时间限制:C/C++1000ms,其他语言:2000ms

内存限制:C/C++256MB,其他语言:512MB

输入

第一行:给出任务完全二叉树的节点数,数值范围[0,1000]

第二行:任务组成的完全二叉树,广度遍历的序列值

第三行:CPU可执行的有限的时间值,数值范围[0,1000]

输出

CPU最高利用率下可执行的任务个数

样例1

输入:

1 2 3 4 5 6 6

输出:

解释：

有限的时间:15

输出:最高利用率可以处理5个任务1+2+3+4+5=15

样例2

输入:

1 2 3 3 4 5 9

输出:

解释：

有限的时间:19

输出:

最高利用率可以处理5个任务1+2+3+4+9=19。

注意虽然1+2+3+3+4+5=18可以处理6个任务,但是CPU仅运行了18个时间，没有满足CPU连续运行时间最长的前提，因此不是最高利用率的选择。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int maxTasks(const vector<int>& tasks, int availableTime) {
    int timeUsed = 0;
    int tasksDone = 0;
    int level = 0;
    int nodesInLevel = 1;

    for (int i = 0; i < tasks.size() && timeUsed + tasks[i] <= availableTime; ++level) {
        int nodesProcessed = 0; 
        int timeInLevel = 0; 

        while (nodesProcessed < nodesInLevel && i < tasks.size() && timeUsed + tasks[i] <= availableTime) {
            timeUsed += tasks[i];
            timeInLevel += tasks[i];
            tasksDone++;
            nodesProcessed++;
            i++;
        }

        if (nodesProcessed < nodesInLevel) {
            break;
        }

        nodesInLevel *= 2;
    }

    return tasksDone;
}

int main() {
    int n; 
    cin >> n;

    vector<int> tasks(n);
    for (int i = 0; i < n; ++i) {
        cin >> tasks[i];
    }

    int availableTime;
    cin >> availableTime;

    cout << maxTasks(tasks, availableTime) << endl;

    return 0;
}

1、找出作弊的人

公司组织了一次考试,现在考试结果出来了，想看一下有没人存在作弊行为,但是员工太多了,需要先对员工进行一次过滤,再进一步确定是否存在作弊行为。

过滤的规则为:找到分差最小的员工ID对(p1,p2)列表,要求p1<p2

员工个数取值范国:O<n<100000

员工ID为整数,取值范围:0<=n<=100000

考试成绩为整数,取值范围:0<=score<=300

解答要求

时间限制:C/C++ 300ms,其他语言:600ms

内存限制:C/C++50MB,其他语言:10OMB

输入

员工的ID及考试分数

输出