P9206 题解

Night_sea_64 · 2023-04-10 21:11:05 · 题解

此题是个简单模拟题。通过 \text{cost}\le 5\times 10^7 可以看出不需要优化。

首先插入排序的代码是这样的（来自 P7910）：

for (int i = 1; i <= n; i++)
    for (int j = i; j >= 2; j--)
        if (a[j] < a[j-1]) {
            int t = a[j-1];
            a[j-1] = a[j];
            a[j] = t;
        }

这里是跟前面一个值作比较然后交换，类比到希尔排序之后，就是跟当前元素前面的第 d 个值作比较然后交换。整个代码就是这样的了：

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[100010];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int cnt=0;
    for(int i=1;i<=m;i++)
    {
        int d;
        scanf("%d",&d);
        for(int i=1;i<=n;i++)
        {
            cnt++;
            int now=i;
            while(now>d)
            {
                if(a[now]<a[now-d])
                {
                    swap(a[now],a[now-d]);
                    now-=d,cnt++;
                }
                else break;
            }
        }
    }
    printf("%d\n",cnt);
    for(int i=1;i<=n;i++)
        printf("%d ",a[i]);
    return 0;
}