5 CPU的任务调度N进程

Question

问题.

队列中有5个CPU和N个任务。您必须使用最少的CPU来处理这些任务。任务的格式是到达时间，处理任务的时间。注意：

1. 最多只能使用5个CPU。如果它不可能在5个CPU，打印-1。
2. 处理任务的时间不应大于10，即(队列中等待的时间+处理任务的时间) <= 10。
3. 如果要处理当前任务，在当前CPU中需要超过10秒，则可以移动到不同的CPU，并检查是否可以在<=10时间内处理该任务。
4. 如果无法在<=10或最多5个CPU中处理任务，请打印-1。

Constraints.

0 <=到达时间<=500 1 <=时间处理任务<= 10 0 <= N<=500您只能使用iostream库。不允许使用STL。时间:T测试用例3秒

Eg:-

输入3 1 6 2 7 3 1输出2

Explanation:

3-N1.6-第一项任务在第一时间到达CPU0，第七次离开(1+6).CPU1使用=1.2 7-第二个任务在时间为2到达CPU0中，并在队列中等待5秒，所以总的处理时间是5+7 > 10，因此它被移到CPU1。使用的CPU=2.3 1-第三个任务到达。它可以进入CPU0或CPU1，因为处理时间分别为5 ( (7-3) + 1 )和7 ( (9-3) + 1 )秒。CPU1是一个新的CPU。因此，task2将在9 (2 + 7)秒内完成，而无需在队列中等待。

我的方法：

1. 最初，认为这是minimum train-platform problem的一个变体。但那是错的。
2. 尝试了一种greedy方法，但它给出了一些有效的解决方案-1。
3. 尝试memoization方法。

递归方法解决了这个问题，但是它被超时了。(怪不得)

保存int、int、int[]状态的可能方法是什么？

我也对同样的迭代解决方案持开放态度。

下面是密码。

#include <iostream>
using namespace std;

#define MAXN 500

int min_cpus_used = 6;

int N;
int arr[MAXN];
int len[MAXN];

void recurse( int task_idx, int cpus_used_so_far, int  exit_time_of_task_in_CPUs[] ){

    if( task_idx == N-1){
        min_cpus_used = min( min_cpus_used, cpus_used_so_far);
        return ;
    }

    if( cpus_used_so_far >= min_cpus_used ){
        return ; //optimization
    }

    for(int i=0; i<cpus_used_so_far ; i++){

        int processing_time = 0;
        int time_in_queue = exit_time_of_task_in_CPUs[i] - arr[task_idx];

        if( time_in_queue < 0 ) // ie processor is free before arrival
            time_in_queue = 0;

        processing_time = time_in_queue + len[task_idx];

        // try with existing CPUs
        if( processing_time <=10){
            int prev =  exit_time_of_task_in_CPUs[i];
            exit_time_of_task_in_CPUs[i] = arr[task_idx] + processing_time;

            recurse( task_idx + 1 , cpus_used_so_far , exit_time_of_task_in_CPUs ); // can we optimize passing array

            exit_time_of_task_in_CPUs[i] = prev;

        }

        // try with new CPU
        if (cpus_used_so_far+1 <= 5){

            int new_cpu_index = cpus_used_so_far + 1 - 1; // converting to zero index

            int prev = exit_time_of_task_in_CPUs[new_cpu_index];

            exit_time_of_task_in_CPUs[new_cpu_index] = arr[task_idx] + len[task_idx] ;

            recurse( task_idx+1 , cpus_used_so_far+1 , exit_time_of_task_in_CPUs );

            exit_time_of_task_in_CPUs[new_cpu_index] = prev;

        }else{
            return ;
        }

    }

}



int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>N;

    for(int i=0;i<N;i++){
        cin>> arr[i] >> len[i];
    }

    int exit_time_of_task_in_CPUs[5]={0};
    recurse(0, 1, exit_time_of_task_in_CPUs);

    if(min_cpus_used==6){
        cout<< -1 <<endl;
    }else{
        cout << min_cpus_used <<endl;
    }

}

请帮助我了解你对优化这个解决方案的想法。

Answer 1

阅读并对C++标准指南进行书签。我后来注意到的数字是从这个引证的。

别写using namespace std;.

但是，您可以在CPP文件(而不是H文件)或函数中放置单独的using std::string;等(参见SF.7)。

#define MAXN 500

不要将#define用于常量或“函数”(⧺ES.31)。

void recurse( int task_idx, int cpus_used_so_far, int  exit_time_of_task_in_CPUs[] ){

最后一个参数是一个指针，这意味着您要将一个指针传递给第一个连续元素。不要像那样传递未知大小的数组。

(提前阅读…)由于它是编译时已知的固定大小，所以将其定义为std::array，这是main中的实际数组和参数(通过引用)。

int min_cpus_used = 6;

int exit_time_of_task_in_CPUs[5]={0};

if (cpus_used_so_far+1 <= 5){

if(min_cpus_used==6){

硬编码魔法数字:这些都是相关的吗？定义一个常量，而不是在整个代码中撒这些常量。

让我们看看…cpus_used_so_far在函数中没有改变，只是在递归时传递了一个不同的值，对吗？在声明中将其标记为const将有助于可读性和分析。

    if (cpus_used_so_far+1 <= 5){
            ⋮
    }else{
        return ;
    }

在结束大括号之前，我花了很长时间才弄清楚else return在函数的末尾做了什么。如果您颠倒逻辑，这将更加清楚:以先决条件测试的方式将例外情况放在第一位。

if (cpus_used_so_far+1 > 5)  return;
⋮

请注意，常规代码没有进一步缩进，因为它不再是嵌套的--它是代码的主要行。

cin.tie(NULL);

不要使用C宏NULL。对于空指针，它是关键字nullptr。

    cout<< -1 <<endl;

不要使用endl。只需使用\n。