算法题目OD

1、有一个特异性的双端队列，该队列可以从头部到尾部添加数据，但是只能从头部移除数据。

小 A 一次执行 2n 个指令往队列中添加数据和移除数据，其中 n 个指令是添加数据(可能从头部也可以从尾部添加) 依次添加 1 到 n , n 个指令是移出数据现在要求移除数据的顺序为 1 到n ，为了满足最后输出的要求, 小 A 可以在任何时候调整队列中的数据的顺序
请问，小 A 最少需要调整几次才能满足移除数据的顺序正好是 1 到 n
输入
3
head add 1
remove
tail add 2
head add 3
remove
remove
第一行一个整数 n，表示数据范围，接下来有 2n 行,其中有 n 行为添加数据指令 head add x 表示从头部添加数据 x，tail add x 表示从尾部添加数据 x 另外 n 行为移除数据指令,指令为 remove 形式,表示移除一个数据 1≤n≤3×10^5$
输出一个整数，表示小 A 要调整的最小次数

2、华为OD 2022Q4 租车骑绿岛_牛客网 (nowcoder.com)

部门组织绿岛骑行团建活动。租用公共双人自行车，每辆自行车最多坐两人，最大载重M。

给出部门每个人的体重，请问最多需要租用多少双人自行车。(应该是最少租用吧?)

输入描述

第一行两个数字m、n，分别代表自行车限重，部门总人数。

第二行，n个数字，代表每个人的体重，体重都小于等于自行车限重m。

0<m<=200
0<n<=1000000

输出描述

最小需要的双人自行车数量。

用例

输入

3 4

3 2 2 1

输出

题目解析

本题需要最少的车辆，即尽可能组合出重量小于等于m的两人组: 尽量让体重最大和体重最小的那两个人一辆车,先把人按体重从大到小排序,如果体重最大 + 体重最小大于自行车载重, 就让体重大的那个人单独一辆车

利用双指针:

例如:

自行车载重: 6

索引: 0 1 2 3 4 5

体重: 6 5 4 3 2 1

left 是最左边那个人 ,索引 0, 体重 6

right 是最右边那个人 , 索引 5,体重 1

一次遍历后

自行车载重: 6

索引: 1 2 3 4 5

体重: 5 4 3 2 1

left 是最左边那个人 ,索引 1, 体重 5

right 是最右边那个人 , 索引 5,体重 1

再次遍历后

自行车载重: 6

索引: 2 3 4

体重: 4 3 2

left 是最左边那个人 ,索引 2, 体重 4

right 是最右边那个人 , 索引 4,体重 2

再次遍历后

自行车载重: 6

索引: 3

体重: 3

此时 left = right = 3,体重为3的这个人单独一辆车

import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line1 = sc.nextLine();
        String[] strings = line1.split(" ");
        // 自行车载重
        Integer load = Integer.parseInt(strings[0]);
        String line2 = sc.nextLine();
        String[] people = line2.split(" ");
        // 体重列表
        List<Integer> weightList = new ArrayList<>();
        for (int i = 0; i < people.length; i++) {
            weightList.add(Integer.parseInt(people[i]));
        }
        // 将每个人按体重由大到小排序
        Collections.sort(weightList, Collections.reverseOrder());
        // 最左边的人体重,也是最大体重
        int left =0;
        // 最右边的人的体重,也是最小体重
        int right = weightList.size() -1;
        int bikeNum =0;
        while (left < right) {
            Integer maxWeight = weightList.get(left);
            Integer minWeight = weightList.get(right);
            // 最大体重 + 最小体重 <= 自行车载重
            if (minWeight + maxWeight <= load) {
                left ++;
                right --;
                bikeNum ++;
            } else {
                // 体重最大的那个人单独一辆车
                left ++;
                bikeNum ++;

            }
        }
        // 剩下最后一个人,单独一辆车
        if (left == right) {
            bikeNum++;
        }

        System.out.println(bikeNum);
    }
}

3、#任务调度

现有一个CPU和一些任务需要处理，已提前获知每个任务的任务ID、优先级、所需执行时间和到达时间。

CPU同时只能运行一个任务，请编写一个任务调度程序，采用“可抢占优先权调度”调度算法进行任务调度，规则如下：

如果一个任务到来时，CPU是空闲的，则CPU可以运行该任务直到任务执行完毕。
但是如果运行中有一个更高优先级的任务到来，则CPU必须暂停当前任务去运行这个优先级更高的任务；
如果一个任务到来时，CPU正在运行一个比他优先级更高的任务时，信道大的任务必须等待；
当CPU空闲时，如果还有任务在等待，CPU会从这些任务中选择一个优先级更高的任务执行，相同优先级的任务选择到达时间最早的任务。
输入描述
输入有若干行，每一行有四个数字（均小于 10^8），分别为任务ID、任务优先级、执行时间和到达时间。

每个任务的任务ID不同，优先级数字越大优先级越高，并且相同优先级的任务不会同时到达。

输入的任务已按照到达时间从小到大排序，并且保证在任何时间，处于等待的任务不超过 10000 个。

输出描述
按照任务执行结束的顺序

测试用例
输入
1 3 5 2
2 1 3 6
3 2 5 11
4 2 6 12
5 3 3 15
1
2
3
4
5
输出
[0]：任务ID；[1]：任务完成时间

1 7
2 10
5 18
3 19
4 25
1
2
3
4
5
解题思路
题目解析
CPU空闲时可执行任务；
优先级高的任务到来会暂停当前任务，在下一个任务到来前无法确认当前任务是否被暂停；
当前任务与上一任务到达时间之差可以明确为CPU空闲时间，该段时间可执行当前任务之前的任务；
需要有个结构可以存储优先级与任务的关系作为待执行任务池，同时需要根据优先级进行排序，此处可以选用TreeMap结构；
相同优先级任务按到达时间执行，可选择链表结构
代码示例
/**

执行任务
@param tasks 待执行任务（按任务到达时间由小到大）
@return 任务执行结果
*/
public List startTask(int[][] tasks) {
// 当前时间
int endTime = 0;
// 执行结果
List result = new ArrayList<>();
// 任务池，key：任务优先级；value：任务链表
TreeMap<Integer, LinkedList<int[]>> pool = new TreeMap<>();

for(int[] task : tasks) {
// 任务到达之前与上一次执行间隙时间，处理该段时间可执行任务
startPoolTask(endTime, task[3] - endTime, pool, result);
// 将当前任务放至任务池
pool.putIfAbsent(task[1], new LinkedList<>());
pool.get(task[1]).add(task);
// 更新时间为结束时间
endTime = task[3];
}

// 任务添加完毕，顺序执行任务池中任务
Map.Entry<Integer, LinkedList<int[]>> entry;
while(!pool.isEmpty()) {
entry = pool.pollLastEntry();
for (int[] task : entry.getValue()) {
endTime += task[2];
result.add(task[0] + “ “ + endTime);
}
}

return result;

}

/**

执行等待队列中CPU任务
@param curTime 当前时间
@param time 可执行CPU任务时间
@param tasks 待执行CPU任务
@param result 执行结果
*/
private void startPoolTask(int curTime, int time, TreeMap<Integer, LinkedList<int[]>> tasks, List result) {
// 不存在可执行时间，直接跳过
if(time <= 0) {
return;
}
// 无等待任务
if(tasks.isEmpty()) {
return;
}
// 获取优先级最高的任务列表
Map.Entry<Integer, LinkedList<int[]>> entry = tasks.lastEntry();
LinkedList<int[]> list = entry.getValue();
// 取出列表中最先到达的任务
int[] task = list.getFirst();
// 任务所需时间大于可执行时间，更新任务所需时间
if(time < task[2]) {
task[2] -= time;
return;
}
// 任务执行完成后从队列中移除，并添加执行结果
list.pop();
result.add(task[0] + “ “ + (curTime + task[2]));
// 若移除后任务列表为空，移除该优先级任务列表
if(list.isEmpty()) {
tasks.remove(entry.getKey());
}
// 执行下一次CPU空闲任务
startPoolTask(curTime + task[2], time - task[2], tasks, result);
}