21天学习挑战赛--执行时长

活动地址：CSDN21天学习挑战赛

题目描述

为了充分发挥GPU算力，需要尽可能多地将任务交给GPU执行，现在有一个任务数组，数组元素表示在这1秒内新增的任务个数且每秒都有新增任务，假设GPU最多一次执行n个任务，一次执行耗时1秒，在保证GPU不空闲情况下，最少需要多长时间执行完成。

输入描述

第一个参数为GPU一次最多执行的任务个数，取值范围[1,10000]。

第二个参数为任务数组长度，取值范围[1,10000]。

第三个参数为任务数组，数字范围[1,10000]。

输出描述

执行完所有任务最少需要多少秒

示例

输入

3

5

1 2 3 4 5

输出

6

说明

一次最多执行3个任务，最少耗时6秒

思考

模拟GPU每秒钟执行任务的情况，循环一次即为一秒，循环次数就是执行时长了。在模拟时，需要一个队列存储等待执行的任务，这里不需要具体实现队列存储任务，可以用一个变量 waitTaskNumber 记录需要执行的任务数量，一个循环中，首先将新增的任务推入队列，也就是加入变量 waitTaskNumber ，然后从队列中取任务执行，也就是减去最大执行任务数n，最后考虑循环停止条件即可。

代码实现

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //取值
        int n = scanner.nextInt();
        int l = scanner.nextInt();
        int[] array = new int[l];
        for (int i=0;i<l;i++) {
            array[i] = scanner.nextInt();
        }
        
        //计时
        int time = 0;
       	//等待执行的任务个数
        int waitTaskNumber = 0;
        while(true) {
            //将新增任务添加进等待执行任务的队列中
            if (time < l) {
            waitTaskNumber += array[time]
            }
            //执行任务
            if (waitTaskNumer <= n) {
                //执行完所有等待任务
                waitTaskNumber = 0;
            }else {
                //执行完n个等待任务
                waitTaskNumber -= n;
            }
            //本秒钟执行完毕，加一
            time ++;
            //判断是否还需要继续执行
            if (time > l && waitTaskNumber == 0) {
                break;
            }
        }
        
        //打印结果
        System.out.println(time);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

总结

博主原文 中的解决思路在时间复杂度上比我此处的想法更优，不应该在无新增任务后继续用循环去执行，可以使用数字计算直接解决，尤其当 waitTaskNumber 数值较大时，计算节省的时间很可观。模拟GPU运行的逻辑也许更好理解，但也会被这理解局限。