CTSC2013算法竞赛：手套问题解析

"CTSC 2013 Day1 是一场著名的算法竞赛，主要涉及的问题是‘手套’分配问题，旨在测试参赛者的逻辑思维和算法设计能力。比赛题目分为不同的难度级别，对时间和内存使用都有严格的限制，并且部分题目设有部分分数。" 在CTSC 2013的第一天竞赛中，有一个名为"手套"的题目，这是一个关于优化资源分配的问题。题目设定是，在一个医疗场景中，有n位医生和m位病人，每个医生可能需要给多个病人做手术。为了防止交叉感染，每位医生在手术过程中必须佩戴手套。手套一旦使用，内外两面都会沾染到不同人的体液，因此不能拆开单独使用，但可以翻转使用。 题目要求参赛者计算出最少需要多少副手套来完成所有的手术，并给出具体的分配方案。每个手术由一对医生和病人组成，手术顺序是已知的。每组测试数据包括n（医生数）、m（病人数）和s（手术数），以及具体的手术配对。 输入格式中，首先读取测试数据组数T，然后对于每组数据，输入n、m、s，接着是s个手术配对（医生编号x和病人编号y）。输出格式则需要给出总共需要的手套数量p，以及每场手术使用的手套详细信息，包括手术编号、使用的手套数量k（1或2）以及手套的字母编号（小写代表未翻转，大写代表翻转使用）。 样例输入和输出展示了如何处理这种情况。例如，对于一组数据，当医生和病人数量分别为2、2和4时，最少需要2副手套，其中第1场手术使用1副手套，第2场手术使用1副手套，而第3场和第4场手术则需要同时使用2副手套，且在第4场中有一副手套需要翻转使用。 数据规模限制了每组测试数据中手术数量s不超过医生与病人总数的乘积，且测试数据组数T不超过10。此外，题目还给出了针对不同难度级别的n和m的范围限制。 解决这个问题需要运用贪心算法或者动态规划，考虑如何有效地分配和翻转手套以达到最少的使用数量。这不仅考验选手的编程技巧，更强调他们在实际问题中的策略选择和优化能力。