题目分析

这是一个模拟题，需要处理多个服务的部署过程。每个服务需要在当前可用机器最多的前 $c_i$ 个数据中心中各部署 $m_i$ 台机器。

算法思路

核心思想

使用归并排序思想来高效处理每次服务后的数据中心排序，避免每次都进行完整的 $O(n \log n)$ 排序。

关键观察

每次服务后，数据中心数组实际上由两部分组成：

1. 被选中的数据中心：前 $c_i$ 个，机器数减少 $m_i$
2. 未被选中的数据中心：剩下的 $n-c_i$ 个，机器数不变

这两部分在各自内部仍然保持有序，因此可以用归并的方法在 $O(n)$ 时间内重新排序。

代码详解

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1,S=5e3+1;
int n,s,a[N],b[N],m,c;

int main(){
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;++i)
        scanf("%d",a+i);
    // 初始降序排序
    sort(a+1,a+n+1,greater<int>());
    
    for(;s--;){
        scanf("%d%d",&m,&c);
        // 使用三指针归并：i指向被选中的数据中心，j指向未被选中的数据中心
        for(int i=1,j=c+1,k=1;k<=n;)
            if(i>c||j<=n&&a[i]-m<a[j])
                // 选择未被选中的数据中心（机器数更大）
                b[k++]=a[j++];
            else
                // 选择被选中的数据中心（减少m后仍然更大）
                b[k++]=a[i++]-m;
        
        // 将排序结果复制回原数组
        for(int k=1;k<=n;++k)
            a[k]=b[k];
    }
    
    // 输出最终结果
    for(int i=1;i<=n;++i)
        printf("%d ",a[i]);
    return 0;
}

算法流程详解

1. 初始化

sort(a+1,a+n+1,greater<int>());

初始时对数据中心按机器数降序排序。

2. 处理每个服务

对于每个服务 $(m_i, c_i)$：

• 被选中的数据中心：a[1] 到 a[c]，机器数减少 $m_i$
• 未被选中的数据中心：a[c+1] 到 a[n]，机器数不变

3. 归并过程

for(int i=1,j=c+1,k=1;k<=n;)
    if(i>c||j<=n&&a[i]-m<a[j])
        b[k++]=a[j++];
    else
        b[k++]=a[i++]-m;

归并逻辑：

• i 指针：遍历被选中的数据中心（1 到 c）
• j 指针：遍历未被选中的数据中心（c+1 到 n）
• k 指针：填充结果数组

选择条件：

• 如果 i 已用完（i>c），选择 j 指向的数据中心
• 如果 j 未用完且 a[i]-m < a[j]，选择 j 指向的数据中心（机器数更大）
• 否则选择 i 指向的数据中心（减少 $m_i$ 后仍然更大）

复杂度分析

• 初始排序：$O(n \log n)$
• 每个服务处理：$O(n)$ 的归并操作
• 总复杂度：$O(n \log n + s \cdot n)$

相比朴素的每次完整排序（$O(s \cdot n \log n)$），这种方法的效率更高。

样例验证

以题目样例为例：

初始：[20, 18, 15, 12, 10]

服务1 (m=3, c=4)：

• 选中：[17, 15, 12, 9]，未选中：[10]
• 归并后：[17, 15, 12, 10, 9]

服务2 (m=4, c=1)：

• 选中：[13]，未选中：[15, 12, 10, 9]
• 归并后：[15, 13, 12, 10, 9]

依此类推，最终得到正确结果。