信息学奥赛CSP 2021-J2：糖果分配与插入排序优化策略

在信息学奥赛入门组复赛CSP 2021-J2的题目中，主要考察了两个算法问题：Candy 分糖果和Insertion Sort 插入排序。这两个题目分别对应着不同的编程挑战和思维策略。 1. Candy 分糖果（题目编号未提供）： - 题目背景：给定n个小朋友和L-R颗糖果，目标是在这些糖果中选取K颗分配给他们，使得K除以n的余数（K mod n）尽可能大。这涉及取模运算和优化选择策略。 - 解题关键：首先，判断是否存在一种情况，即K等于n-1时，可以直接满足题目要求，因为此时余数最大为n-1。如果存在，输出这个值。如果K不能取n-1，考虑使用取模运算（R mod n）作为结果。如果L到R的糖果范围内的最大值减去n后与L的余数之和小于或等于R，那么K取n-1仍然能满足条件，输出n-1；否则，直接输出R mod n。 2. Insertion Sort 插入排序： - 题目描述：面对一个长度为n的数列，需处理Q次询问和修改操作。询问要求对当前数列进行插入排序并找到某个特定位置元素排序后的正确位置。原始代码显示插入排序是稳定的，意味着相同数值的相对顺序不会改变。 - 算法优化：原题给出的解决方案对于每次修改后重新排序是低效的，时间复杂度过高。为了提高效率，注意到如果数列在修改前是有序的，那么只需将修改后的数与左右邻居进行比较，更新它们的位置信息。引入辅助数组存储位置变化，这样在处理修改和查询时，只需对已排序的部分进行简单的调整，从而大大降低了时间复杂度。 CSP 2021-J2主要考察了参赛者对基础算法的理解和优化能力，尤其是对取模运算、排序算法（如插入排序）在实际场景中的应用以及如何通过数据结构优化来降低时间复杂度。同时，题目也强调了算法的稳定性，这对于理解和实现正确的排序算法至关重要。参赛者需要具备扎实的数据结构基础，灵活运用算法策略，以高效地解决这类问题。