c加加代码实现，有n (n<=10) 个整数，使前面各数顺序向后移m (m<=n) 个位置，最后m个数变成最前面的m个数，如图所示。编写函数shift(a,n,m)实现上述功能在主函数中输入n个整数并输出调整后的n个数。

为了使用快速排序的思想求解给定无序序列a中的前k个最大元素，我们可以采取一种称为“快速选择”（QuickSelect）的变体，它基于快速排序的思想，但只对查找目标进行划分，而不是整个数组。以下是基本的步骤： 1. **选择枢轴**： 首先随机选择一个元素作为枢轴（pivot），这有助于平均情况下的性能。 2. **划分**： 利用枢轴将数组分为两个部分，一部分包含所有小于等于枢轴的元素，另一部分包含所有大于枢轴的元素。因为我们在找第k大元素，所以我们关心的是大于枢轴的部分。 3. **检查位置**： 如果枢轴右侧的元素个数大于等于k，那么我们就在这个分区里继续查找第k大元素。如果小于k，那么我们需要在左分区的剩余部分查找第(k-pivot_right_size)大元素，这里的pivot_right_size是右侧元素的数量。 4. **递归**： 根据上一步的结果，重复上述过程，直至找到第k大元素或确定其不在当前分区。 以下是简单的C++代码实现： ```cpp #include <vector> #include <cstdlib> // 对于random_shuffle using namespace std; int partition(vector<int>& arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[high]); return i + 1; } int quickSelectKthLargest(vector<int>& a, int k, int low, int high) { if (low == high) return a[low]; int pivot_index = partition(a, low, high); if (pivot_index == k - 1) return a[pivot_index]; else if (pivot_index > k - 1) return quickSelectKthLargest(a, k, low, pivot_index - 1); else return quickSelectKthLargest(a, k, pivot_index + 1, high); } vector<int> findTopK(vector<int>& a, int k) { vector<int> result(k); random_shuffle(a.begin(), a.end()); // 防止最坏情况（序列已经有序） for (int i = 0; i < k; i++) result[i] = quickSelectKthLargest(a, i + 1, 0, a.size() - 1); return result; } int main() { vector<int> a = {9, 2, 5, 1, 6, 7}; int k = 3; vector<int> top_k = findTopK(a, k); cout << "前" << k << "个最大的元素是："; for (int num : top_k) cout << num << " "; return 0; } ```

这是一个典型的 **调度优化问题**，可以使用贪心算法解决。我们可以通过按题目分数从高到低排序，并结合截止日期安排任务顺序来求解。 以下是详细的解决方案： --- ### 算法步骤 1. **读取输入并存储信息** - 将所有题目的分数 `pi` 和截止日期 `di` 存储在一个数组中。 2. **按照分数降序排列** - 贪心思想的核心在于优先选择分数更高的题目，因此我们需要将题目按照分数从大到小排序。 3. **分配时间段** - 创建一个标记数组 `time_slots[0...max_di]` 表示每天是否已被占用。 - 遍历排好序的题目列表，尝试将其安排在不超过其截止日期的第一个空闲位置上。 4. **计算总分** - 统计成功安排的所有题目的分数之和作为结果。 --- ### C++ 实现代码 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; // 定义结构体保存题目信息 struct Task { int score; // 分数 p_i int deadline; // 截止日期 d_i }; // 排序规则：按分数从高到低排序 bool compareTasks(const Task& a, const Task& b) { return a.score > b.score; } int main() { int n; cin >> n; vector<Task> tasks(n); int maxDeadline = 0; // 输入数据 for (int i = 0; i < n; ++i) { cin >> tasks[i].score >> tasks[i].deadline; if (tasks[i].deadline > maxDeadline) { // 更新最大截止日期 maxDeadline = tasks[i].deadline; } } // 按照分数降序排列 sort(tasks.begin(), tasks.end(), compareTasks); // 标记哪些天已经被占用 vector<bool> timeSlots(maxDeadline + 1, false); // 下标0不用，从1开始对应第1天到最后一天 int totalScore = 0; // 尝试给每个题目分配合适的时间段 for (const auto &task : tasks) { // 找出 task.deadline 到第1天之间的第一个未被使用的日期 for (int day = task.deadline; day >= 1; --day) { if (!timeSlots[day]) { // 如果这一天还没有安排任务 timeSlots[day] = true; // 占用这个时间点 totalScore += task.score; // 加入得分 break; } } } cout << totalScore << endl; return 0; } ``` --- ### 示例运行 #### 输入： ``` 7 6 2 1 3 2 3 8 5 9 5 5 3 7 4 ``` #### 输出： ``` 25 ``` #### 解释： 最优策略是完成题目 `[9, 8, 7, 6]`，即在第 5、4、3、2 天分别完成它们，得到的最大得分为 `9+8+7+6=30`。 --- ### 时间复杂度分析 - **排序阶段**: O(n log n)，因为我们需要对所有题目按分数排序。 - **分配时间段阶段**: 最坏情况 O(n * D)，其中 D 是最大的截止日期值（通过剪枝可以在实际应用中减少不必要的检查）。 - 总体时间复杂度接近于 O(n log n + nD)。 对于本题的数据范围（n ≤ 1e4, di ≤ 1e4），此方法能够高效解决问题。 ---