不知道你是不是也遇到过这种情况在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天没排而我扫一遍所有未使用的人发现剩下这些人里能满足“未来至少某一天可以值班”的人数总和都不够填满剩余天数那其实已经不可能排完了。这个剪枝比第一个更狠因为它从全局判断了可行性而不是只看当前这一天。这种剪枝在数据量小的时候效果不明显但如果你遇到的是n12、m12这种接近排列上限的测试点它能砍掉大量注定失败的中间状态。我自己测试过加了这个剪枝后极端数据从跑满几秒降到零点零几秒。不过要说明这个剪枝写起来要比第一个稍微复杂一点所以我给出的提交版代码里保留了更简单的“当日无候选”剪枝把全局剪枝放在注释里给你参考你可以在本地拷贝一份加强版去测试。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, jm-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 用一张表总结这四个坑现象最容易的原因我的对策显示格式错误行尾多余空格、空行不对统一用“先空格后数字”的输出模式答案整体偏一编号0基、1基搞混读入时减1输出时加1内部只用0基个别测试点答案错误没有处理无解输出用found变量标记结束后统一判断运行错误或崩溃数组开小、越界按题面上限并留余量定义数组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扛不住了怎么办如果题目数据一下子放大到n20、m20纯DFS哪怕加剪枝也可能超时。到了这个规模通常可以考虑状态压缩动态规划用一个整数的二进制位表示“哪些人已经被安排”dp[state]表示达到这个人员使用状态时是否可行、或者有多少种方案。人一多二进制位刚好够用转移时枚举下一天安排哪个还没用的人。不过对PTA“值班安排”这道入门题来说数据量远没有到非用状压不可的程度。我把这个思路提在这里只是给你指一个后续进阶的方向。先把回溯版本吃透再去学状压DP这条路走下来会顺很多。最后说个我自己刷这类题的小习惯。我每次看题面都会先写一行注释把题目规则翻译成“约束条件”列在旁边比如“每个人最多1次”“每天正好1人”“无解输出No Solution”。这行注释看起来不起眼但能让你在写代码的时候始终保持模型清晰不会写一半被题目的故事描述带偏。等代码提交通过之后这行注释还能帮你快速回忆起当时的设计思路回头整理题解的时候也省事。希望你也能用这个思路把“值班安排”这题干净利落地拿下来。