hw机试后感

case1，简单，逗号隔开的数组，找出素数去重，排序

case2，动态规划，8个任务，分布式计算，给出每个任务的子任务数量和所需服务器数量，服务器数量必须全部满足才能运行一个大任务。

我将其抽象成图的最大路径查找，利用递归，最后因为判断条件未考虑全，时间只剩5min不想改了就直接教了，过了40%。

提交的代码

#include <iostream>

using namespace std;

struct task
{
    int file_num, service_num;
};


    int n, files = 0, service = 0, max_files = 0;
    int sta[8], p = 0;
    task tasks[8];

    void find_maxfiles(int a)
    {
        service += tasks[a].service_num;
        files += tasks[a].file_num;
        if(service == n && files > max_files)
        {
            max_files = files;
            service -= tasks[a].service_num;
            files -= tasks[a].file_num;
        }
        else if(service < n)
        {
            sta[p++] = a;
            int flag;
            for(int i = 0; i < 8; i++)
            {
                flag = 0;
                for(int j = 0; j < p; j++)
                    if(sta[j] == i)
                    {
                        flag = 1;
                        break;
                    }
                if(flag == 1 || i == a)
                    continue;
                find_maxfiles(i);
            }
        }
        p--;
    }
int main()
{
    tasks[0].file_num = 300;
    tasks[0].service_num = 20;
    tasks[1].file_num = 500;
    tasks[1].service_num = 30;
    tasks[2].file_num = 620;
    tasks[2].service_num = 50;
    tasks[3].file_num = 370;
    tasks[3].service_num = 30;
    tasks[4].file_num = 400;
    tasks[4].service_num = 50;
    tasks[5].file_num = 450;
    tasks[5].service_num = 30;
    tasks[6].file_num = 380;
    tasks[6].service_num = 40;
    tasks[7].file_num = 150;
    tasks[7].service_num = 10;

    cin >> n;
    if(n < 10)
        return 0;
    if(n >= 260)
    {
        cout << 3170;
        return 0;
    }
    n = n - n % 10;
    for(int i = 0; i < 8; i++)
    {
        files = 0;
        service = 0;
        p = 0;
        find_maxfiles(i);
    }

    cout << max_files;
    return 0;
}

改进算法：考虑到如下情况：总数为260，加入除了其中一个需要50个服务器的任务外，其他服务器都满足，此时 n应为210；若n在210到260区间，也只能是输出满足210的条件；（未经过hw机试的测试用例验证，仅自己模拟数据，感觉应该能过）

#include <iostream>

using namespace std;

struct task
{
    int file_num, service_num;
};


    int n, files = 0, service = 0, max_files = 0;
    int sta[8], p = 0;
    task tasks[8];

    void find_maxfiles(int a)
    {
        service += tasks[a].service_num;
        if(service > n)
        {
            service -= tasks[a].service_num;
            return ;
        }
        files += tasks[a].file_num;
        if(service <= n)
        {
            if(files > max_files)
            {
                max_files = files;
            }
            sta[p++] = a;
            int flag;
            for(int i = 0; i < 8; i++)
            {
                flag = 0;
                for(int j = 0; j < p; j++)
                    if(sta[j] == i)
                    {
                        flag = 1;
                        break;
                    }
                if(flag == 1 || i == a)
                    continue;
                find_maxfiles(i);
            }
            service -= tasks[a].service_num;
            files -= tasks[a].file_num;
        }
        p--;
    }
int main()
{
    tasks[0].file_num = 300;
    tasks[0].service_num = 20;
    tasks[1].file_num = 500;
    tasks[1].service_num = 30;
    tasks[2].file_num = 620;
    tasks[2].service_num = 50;
    tasks[3].file_num = 370;
    tasks[3].service_num = 30;
    tasks[4].file_num = 400;
    tasks[4].service_num = 50;
    tasks[5].file_num = 450;
    tasks[5].service_num = 30;
    tasks[6].file_num = 380;
    tasks[6].service_num = 40;
    tasks[7].file_num = 150;
    tasks[7].service_num = 10;

    cin >> n;
    if(n < 10)
        return 0;
    if(n >= 260)
    {
        cout << 3170;
        return 0;
    }
    n = n - n % 10;
    for(int i = 0; i < 8; i++)
    {
        files = 0;
        service = 0;
        p = 0;
        find_maxfiles(i);
    }

    cout << max_files;
    return 0;
}

case3：给出一个数组，要求按输入的命令做出操作，U a b k 为更新从下标a到下标b（含）的值为其的k次方。可能是超过64bit的大数，因此要对1234567891取余数； C a b为求下标a 到 b（含）的数的和，并输出。

原谅我太菜，之前ccf就卡在大数上面了，当时思路也有，最简单的，用string进行操作多次的加减操作，但怕时间复杂度太大，而且因为第二题刚开始打算偷鸡，浪费了半个小时，导致时间也不太够了，放弃了。

hw机试后感

全站热榜