话不多说，直接开始分析。

题目

查看题目

题意分析

给定 $n$ 个服务器，每个服务器有最大处理能力。给定 $k$ 个任务，每个任务需要占用一定的服务器处理能力。要求找到一个分配方案，使得每个任务都能分配到一个服务器，并且分配方案的服务器编号字典序最小。如果找不到分配方案，输出 -1。这个题意我认为大家是可以秒掉的。

题目解法

思路

输入：

读取服务器数量 $n$ 、任务数量 $k$ ，以及每个服务器的处理能力 a[i] 和每个任务的需求 b[i]。

DFS（深搜）：

从第一个任务开始，依次为每个任务分配服务器。
优先尝试编号较小的服务器，保证字典序最小。
使用 vis[i] 数组标记服务器 i 是否已被分配。
如果找到一个可行的分配方案，设置 f 为 true 并输出结果。
如果回溯后找到可行方案，则直接返回，否则继续尝试。

输出：

如果 f 为 false，说明没有找到可行的分配方案，输出 -1 (结尾代码 if(!f)，也可以用 f == 0 代替)。

复杂度分析

时间复杂度

O(n^k)

，其中

n

是服务器的数量，

k

是任务的数量。这是因为最坏情况下需要尝试所有可能的分配方案。

代码

以下是核心代码：

void dfs(int cur)
{
    if (cur == k)
    {
        f = true;
        for (int i = 0; i < k; i++)
        {
            printf("%d%c", p[i] + 1, (i == k - 1) ? '\n' : ' ');
        }
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (!vis[i] && a[i] >= b[cur])
        {
            vis[i] = true;
            a[i] -= b[cur];
            p[cur] = i;
            dfs(cur + 1);
            if (f)
                return;
            a[i] += b[cur];
            vis[i] = false;
        }
    }
}

以下是完整代码：

（建议先看完核心代码再参考）

#include <iostream>
#include <cstdio>

using namespace std;

int n, k;
int a[7], b[7], p[7];
bool vis[7];
bool f = false;

void dfs(int cur)
{
    if (cur == k)
    {
        f = true;
        for (int i = 0; i < k; i++)
        {
            printf("%d%c", p[i] + 1, (i == k - 1) ? '\n' : ' ');
        }
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (!vis[i] && a[i] >= b[cur])
        {
            vis[i] = true;
            a[i] -= b[cur];
            p[cur] = i;
            dfs(cur + 1);
            if (f)
                return;
            a[i] += b[cur];
            vis[i] = false;
        }
    }
}

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

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

    for (int i = 0; i < k; i++)
    {
        cin >> b[i];
    }

    dfs(0);

    if (!f)
    {
        cout << "-1" << endl;
    }

    return 0;
}

Luogu P8838 题解

题目