自动搬运

查看原文

来自洛谷，原作者为

	Night_sea_64 距离省选还有 +inf 天。

搬运于2025-08-24 22:46:19，当前版本为作者最后更新于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;
}