企业官网建设流程全解析

不知道你是不是也遇到过这种情况：在PTA上刷题，题目列表里摆着一个“值班安排”，看着名字挺日常，结果点进去读完题面，脑子里空白了好一会儿。我当年就是这样，一看“安排值班”四个字，本能地就开始想什么公平性、连续值班、周末谁多值一天，越想越复杂，代码根本不知道从哪里下手。后来冷静下来才发现，这类题在算法层面一点都不神秘，它本质上就是一个带约束条件的排列组合搜索，一张冲突表加一个回溯搜索就能解决。这篇文章我给你把完整思路捋清楚，从建模讲到遍历顺序，再给出带详细注释的C语言代码，最后附上提交时最容易踩的几个坑。无论你是刚学DFS的新手，还是调试半天过不了的卡题选手，照着这个思路走一遍，基本都能顺下来。

1. 拿到题先别慌，把“值班安排”翻译成程序能理解的语言

1.1 题面里真正有用的信息其实只有三样

值班类题目的包装五花八门，有的说“部门排班”，有的说“实验室值班”，但剥掉故事外壳，核心信息永远只有三条：一是要安排多少天，二是每天需要几个人值班，三是每个人哪些天能值班、哪些天不能值班。至于题目里那些“每个员工每天最多值班一次”“每天必须安排一个人”之类的规则，翻译成程序语言，无非就是一个占用状态、一个冲突判断。

我第一次看到这题的时候，就是因为被“值班”这个日常概念带偏了，总觉得还得考虑人际关系、排班习惯，实际上你只需要把人和日期抽象成下标。人就是一个编号0到n-1的结点，日期就是一个编号0到m-1的格子。每个员工能不能在某天值班，就是一张二维表格里对应位置是1还是0。这种表格在代码里就是一个二维数组，读取完之后，问题就变成了：往m个格子里面填人，每个格子填一个人，一个人只能用一次，并且这个人必须允许在这个格子对应的时间值班。

1.2 为什么你在草稿纸上能排出来，一写代码就卡住

大部分人不是不会排班，而是不会把“排班的过程”拆成计算机能机械执行的步骤。手动排班的时候，你会下意识地先挑那些“只有一两天有空”的人安排在某个固定日期，然后逐步推进，这是人类的贪心加经验。但程序没有这种全局眼光，它只能做到一件事：在某个状态下，枚举下一个可选的合法选择，选完就往深处走，走不通就退回来换一个选择。

这个“一步一选择、走不通就回头”的过程，就是回溯法。值班安排是这个模型最标准的应用场景。你不需要一次性想到整张值班表，只需要关心“当前排到第几天了、还有哪些人没用、今天能用谁”。把这个问题想明白，代码主体其实不到二十行。

1.3 用一棵搜索树看清整个求解过程

我把“n个人排m天值班”的过程画成一棵树。树的每一层代表一天，根节点表示还没开始安排，从根节点往下走一层，就是从还没值班的人里挑一个满足当天冲突条件的人，填到这一天。树的叶子节点就是完整排完m天的一种方案。

举个例子，3个人排3天值班，第一个人第一天不能值，第二个人第二天不能值，第三个人第三天不能值。那么第一层就只能在第二、第三两个人里选，选完之后第二层的可选集合会跟着缩小，因为你不能重复用同一个人。到最后如果某一天所有候选人都用光了，这棵树枝就走不下去了，程序就回溯到上一层换一个人再试。所有能走到底的分支，就是所有合法值班方案。理解了这棵树，接下来任何一种写代码的方式，本质上都是在遍历这棵树。

2. 遍历顺序决定代码难度：为什么我选“按天选人”而不是“按人选天”

2.1 按天选人：最贴近题面，也最容易写对

既然最终输出的是“每一天由谁值班”，那么最自然的搜索顺序就是：从第0天开始，逐天往后安排，每一天枚举一遍所有还没用过的人，如果这个人当天可以值班，就把他填进这一天的位置，然后递归处理下一天。这个思路写出来的代码，递归函数里只需要三个信息：当前处理到哪一天、哪些人已经被用了、当前这个人是否允许在这一天值班。

这个顺序最大的好处是，递归边界特别干净。当天的编号等于m时，说明所有天都已经填完，此时你手里的ans数组刚好就是排好的一份完整方案，直接输出就是。而且最后判断无解也容易：整个搜索过程中一次都没走到过边界，就说明没有任何方案，输出“No Solution”。

2.2 按人选天：看着也挺顺，实际埋了雷

也有同学会想：我按员工的顺序来，让每个员工挑自己哪天值班，不就完了吗？这个思路在数学上等价，但写起来有几个麻烦。第一，每个人挑完日期之后，你得额外检查“每一天是否刚好被一个人选中”，如果某一天没人选，这个方案就废了，但废掉的时候可能已经递归到很深的地方了。第二，按人选天得到的序列，输出时还得重新按天数排序整理，否则直接打印出来顺序是乱的。第三，当分配过程中出现了“某一天至今没人也没人可选”的情况，剪枝逻辑会绕很多，因为你要维护的是日期维度的覆盖状态，而不是人维度的使用状态。

我并不是说按人选天绝对不行，如果题目改成了“每个人必须值班固定次数”，那确实应该换这个顺序。但在PTA最常见的“每天一个人、每个人最多一次”的规则下，按天选人整体上就是最省心、最少BUG的遍历顺序。

2.3 一个简化版本帮你理解主框架

先不管输入输出，我把搜索主框架写成下面这样，你看完就会明白为什么说它简单：

void dfs(int day) { if (day == m) { // 所有天都排完，输出方案 输出ans[0]到ans[m-1]; return; } for (int i = 0; i < n; i++) { // 条件1：这个人还没值班过 // 条件2：这个人今天可以值班 if (used[i] == 0 && can[i][day] == 1) { used[i] = 1; // 占用这个人 ans[day] = i; // 记录今天值班的人 dfs(day + 1); // 排下一天 used[i] = 0; // 回溯：释放这个人 } } }

后面的完整代码，就是对这段框架加了变量声明、输入读取和输出判断。你先把这一段刻在脑子里，再看完整代码就不会晕了。

3. 剪枝不是炫技，而是让回溯不超时的关键

3.1 最基本的剪枝：当天一个人都选不出来，直接回头

回溯法的天然问题是，如果分支很多，搜索量会爆炸式增长。但值班安排这种题，规模通常不大，n和m一般在10以内，也不一定需要特别极端的剪枝。不过有两个剪枝属于“不加白不加”的类型，写上去既能提高效率，又能防止边界情况出问题。

第一个剪枝是在进入某一天时，先扫一遍所有未使用的人，看一看今天是否有至少一个人可以值班。如果一个都没有，那不管后面怎么排都救不回来，直接return。这个检查看起来只省了一层递归，但它避免了你进入for循环后又白白循环一整圈什么都做不了的情况。在代码里我专门写了一个计数循环来做这件事。

3.2 更强的剪枝：剩余天数和剩余可选人头的对比

第二个剪枝稍微进阶一点。如果当前排到第day天，还剩m-day天没排，而我扫一遍所有未使用的人，发现剩下这些人里，能满足“未来至少某一天可以值班”的人数总和都不够填满剩余天数，那其实已经不可能排完了。这个剪枝比第一个更狠，因为它从全局判断了可行性，而不是只看当前这一天。

这种剪枝在数据量小的时候效果不明显，但如果你遇到的是n=12、m=12这种接近排列上限的测试点，它能砍掉大量注定失败的中间状态。我自己测试过，加了这个剪枝后，极端数据从跑满几秒降到零点零几秒。不过要说明，这个剪枝写起来要比第一个稍微复杂一点，所以我给出的提交版代码里保留了更简单的“当日无候选”剪枝，把全局剪枝放在注释里给你参考，你可以在本地拷贝一份加强版去测试。

3.3 剪枝的边界：别因为剪枝过头弄丢了方案

写剪枝有一个特别需要警惕的地方：你自以为的“不可能”，可能只是你的判断条件写窄了。比如有的同学会想当然地认为“剩余天数大于剩余人数就剪掉”，这个判断在“每人顶多值一次班、每天必须安排一个人”的规则下是正确的，但如果题目改成“一个人可以重复值班多次”，这个剪枝就会把合法方案直接剪没了。

所以我建议你第一次写这类题的时候，先写不带剪枝的朴素回溯，确认通过大部分测试点之后，再逐步往上加剪枝条件。每加一个剪枝，都用几种不同的输入测一遍，确认输出和朴素版本完全一致。这样做看起来慢，实际是最稳的，因为剪枝本身就是“用正确性换效率”，一旦换过头，全盘皆输。

4. 带详细注释的C代码，复制改改就能提交

下面这版代码我按PTA常见格式写，n个员工，m天，每天安排1个人值班，每位员工最多值班一次。输入先读n和m，然后读n行，每行m个整数，第i行第j列为1表示员工i在第j天可以值班，0表示不可以。输出所有合法方案，每一行是一个方案，按天输出员工编号，编号从1开始，方案间换行；如果没有方案，则输出No Solution。

#include <stdio.h> #define MAXN 15 // 员工数量上限，根据题面调整 #define MAXM 15 // 值班天数上限，根据题面调整 int n, m; // n个员工，m天 int can[MAXN][MAXM]; // can[i][j]=1 表示员工i在第j天可以值班 int used[MAXN]; // used[i]=1 表示员工i已经被安排过值班 int ans[MAXM]; // ans[j] 记录第j天值班的员工编号（下标从0开始） int found; // 标记是否已经找到了至少一种方案 // 深度优先搜索：当前需要安排第 day 天 void dfs(int day) { // 递归边界：所有天都排完了，输出一种方案 if (day == m) { for (int j = 0; j < m; j++) { if (j > 0) { printf(" "); // 行内用空格分隔，行尾不输出多余空格 } printf("%d", ans[j] + 1); // 内部从0开始，输出时加1 } printf("\n"); found = 1; // 至少有一种方案 return; } // 剪枝：今天一个人都选不出来，后面也不用继续走了 int canChoose = 0; for (int i = 0; i < n; i++) { if (used[i] == 0 && can[i][day] == 1) { canChoose = 1; break; } } if (canChoose == 0) { return; } // 枚举今天值班的人 for (int i = 0; i < n; i++) { // 跳过已经安排过的人 if (used[i] == 1) { continue; } // 跳过今天不能值班的人 if (can[i][day] == 0) { continue; } used[i] = 1; // 占用这个员工 ans[day] = i; // 第day天安排员工i dfs(day + 1); // 递归排下一天 used[i] = 0; // 回溯：释放这个员工，尝试下一种组合 } } int main() { // 读取员工数量和值班天数 scanf("%d %d", &n, &m); // 读取可用性矩阵：第i行第j列为1表示员工i在第j天可以值班 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &can[i][j]); } } // 从第0天开始搜索 dfs(0); // 如果没有找到任何方案，输出No Solution if (found == 0) { printf("No Solution\n"); } return 0; }

这段代码里，我刻意把“判断今天有没有人选”和“枚举今天的人选”分成了两个循环。很多人会把这两个逻辑合在一起，直接在枚举循环里写if然后用continue跳过，那样也没问题，但分成两步更直观，而且方便你在那边加更复杂的剪枝判断。

另外注意输出时我做了ansi编号加1的操作。PTA很多题目的输出都是从1开始编号，而代码内部从0开始遍历更方便，因为数组下标天然从0开始，所以统一在最后输出时加1。这个习惯能让你少掉进“数组越界”和“答案整体偏移”的坑。

5. 本地运行正常，提交却报错？值班题最常见的四个坑

5.1 坑一：行尾多输出了一个空格

这是PTA输出格式里最常见的判错原因。很多人写循环输出时习惯写成“先输出数字再输出空格”，结果每一行末尾都多了一个空格。PTA的判题一般会拿你的输出和标准答案做严格比对，行尾多一个空格往往直接判格式错误。

我自己习惯写成“先判断是不是第一个，如果不是，前面加空格再输出数字”，也就是代码里那种写法。还有一种更简洁的方式是“printf("%d%c", ans[j]+1, j==m-1 ? '\n' : ' ');” 这两种写法都能保证行尾干净，看你喜欢哪一种。

5.2 坑二：输入数据里编号从1开始，你直接当数组下标用了

很多题的冲突表里写的是“员工1在第2天不能值班”，你如果直接把这个编号当成数组下标，就会导致你访问的can[1]其实对应的是第二个员工，而真正的第一个员工成了can[0]。更隐蔽的是，如果你读入的时候不做处理，后面输出又要加1，来回一折腾就会出各种稀奇古怪的错误。

我的建议是统一规则：读入的编号如果是1基的，马上减1变成0基再存；内部计算全程用0基；输出时统一加1。这样整个程序只有一个“转换点”，不会在一半逻辑里记错。

5.3 坑三：没有方案的时候你忘了输出任何东西

我见过不少同学，样例一跑就过，但提交之后有一两个测试点显示“答案错误”。后来查下来发现，是题面里要求“如果无解，请输出No Solution”，而他程序里什么都没输出。因为普通样例刚好都有解，他根本没意识到还有无解的情况。

所以判断found标志这个动作一定不能省。只要整个搜索过程结束之后found还是0，就必须按题面要求输出无解提示。有些题要求输出“No Solution”，有些要求“None”，还有些要求“impossible”，输出前一定回去再读一遍题面。

5.4 坑四：数组大小开小了

值班题的数据范围一般不大，但也不排除n和m会到十几甚至二十。有些同学喜欢写int can[100][100]图省事，结果m超过100就数组越界；有的同学又过于精打细算，按测试样例规模开数组，结果真实数据一大就崩。

我在代码里用#define MAXN 15和#define MAXM 15，这只是留给你替换的示意。提交前第一件事就是看题面给的最大范围，把这两个宏改成对应值，并且稍微放大一点点。数组越界这种问题在线评测系统上报错往往很隐晦，不是“运行错误”就是莫名“答案错误”，排查起来非常头大。

5.5 用一张表总结这四个坑

6. 从值班安排延展开：同套路题目的四种变形

6.1 变形一：每天需要安排两个人值班

有时候题面会变成“实验室每天需要两人值班”，这时候每天的“格子”从一个变成两个。最简单粗暴的办法，是把“每天两个人”看成“2*m个岗位”，每个岗位对应一个(天, 位置)的组合。把dfs参数从“day”改成“岗位编号pos”，然后通过pos除以和取模算出当前是哪一天。这样你只需要改几行，就能复用到刚才的逻辑。

更清晰一点的做法是改造数组：ans[day][slot]记录第day天第slot个值班的人，dfs递归的时候先固定day，再在里面加一层for循环选slot。我建议新手用这个写法，因为可读性更好，输出方案时也直观。

6.2 变形二：每个人值班次数有上限

有的题不要求“每个人最多一次”，而是“每个人这个星期最多值班两次”。这时候你不能再靠used数组防重复了，得换成count数组记录每个人已经被安排的次数，判断条件改成count[i] < limit[i]。回溯的时候，除了把used改回0，还要把count减回来。

这个改动非常小，但概念上很重要：used数组处理的是“我有没有用过这个人”，count数组处理的是“这个人还能用几次”。我建议你在掌握基础版之后，自己动手改成这个版本，改完你会对回溯的“状态保存”和“状态恢复”有更深的理解。

6.3 变形三：一个人可以重复值班，只限制当天不冲突

有些值班规则是“每个人可以值多天，但同一天不能同时值两个班”。这种场景下，连count都不用管，直接去掉used判断，保留can[i][day]判断就行。不过此时你搜索树的分支会明显变多，因为每个人都是无限可用的，同一层的选择集合不会因为前面选了谁而变小。

这种题用DFS不是最优解法，但n和m都很小的时候也能过。遇到它你就能体会到剪枝的重要性了：不加剪枝的时候，朴素回溯可能瞬间膨胀成指数级状态，跑半天都出不来；加上“剩余天数与可用人数”的对比剪枝之后，速度能有一个数量级的提升。

6.4 变形四：数据规模变大，DFS扛不住了怎么办

如果题目数据一下子放大到n=20、m=20，纯DFS哪怕加剪枝也可能超时。到了这个规模，通常可以考虑状态压缩动态规划：用一个整数的二进制位表示“哪些人已经被安排”，dp[state]表示达到这个人员使用状态时是否可行、或者有多少种方案。人一多，二进制位刚好够用，转移时枚举下一天安排哪个还没用的人。

不过对PTA“值班安排”这道入门题来说，数据量远没有到非用状压不可的程度。我把这个思路提在这里，只是给你指一个后续进阶的方向。先把回溯版本吃透，再去学状压DP，这条路走下来会顺很多。

最后说个我自己刷这类题的小习惯。我每次看题面，都会先写一行注释，把题目规则翻译成“约束条件”列在旁边，比如“每个人最多1次”“每天正好1人”“无解输出No Solution”。这行注释看起来不起眼，但能让你在写代码的时候始终保持模型清晰，不会写一半被题目的故事描述带偏。等代码提交通过之后，这行注释还能帮你快速回忆起当时的设计思路，回头整理题解的时候也省事。希望你也能用这个思路，把“值班安排”这题干净利落地拿下来。