自动搬运

查看原文

来自洛谷，原作者为

	ghj1222 阿绫最可爱啦

搬运于2025-08-24 21:31:40，当前版本为作者最后更新于2018-09-03 20:02:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分享一个非正解的做法

本题解内存最低($\le1\rm MiB$)

但是不开O2会tle

思路：每个数字仅会更新出1个新的数字，而且这个新数字比旧数字最多也就大70多。所以这里还是利用“筛数”的思想枚举所有数字筛数字，但这里我开一个小根堆来存储当前已经被发现不是自我数但是还未被遍历到的数字。从小到大遍历所有数字，如果堆是空的，或者堆顶(也就是堆里最小数字)不是当前遍历数字说明这个数字是自我数，统计进ans,输出ans即可

对于k个询问，我们从小到大排序离线操作，再开一个指针pos表示当前询问查询到哪个询问，并随着i的更新来更新询问。最后按照初始id把询问排序回去输出。
具体可见代码实现：

#include <bits/stdc++.h>
using namespace std;

struct ask
{
	int id, x, y;
}a[5010];

int n, k, tot, ans, pos;
priority_queue<int, vector<int>, greater<int> >q;

bool cmp1(const ask &x, const ask &y)
{
	return x.x < y.x;
}

bool cmp2(const ask &x, const ask &y)
{
	return x.id < y.id;
}

int make(int x)
{
	int res = x;
	while (x > 0)
	{
		res += x % 10;
		x /= 10;
	}
	return res;
}

int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= k; i++)
	{
		a[i].id = i;
		scanf("%d", &a[i].x);
	}
	sort(a + 1, a + 1 +k, cmp1);
	for (int i = 1; i <= n; i++)
	{
		if (q.empty() || q.top() != i)
		{
			tot++;
			if (a[pos].x < i)
				pos++;
			while (a[pos].x == tot)
			{
				a[pos].y = i;
				pos++;
			}
			pos--;
			ans++;
		}
		else
			while (!q.empty() && q.top() == i)
				q.pop();
		q.push(make(i));
	}
	printf("%d\n", ans);
	sort(a + 1, a + 1 + k, cmp2);
	for (int i = 1; i <= k; i++)
		printf("%d%c", a[i].y, i == k ? '\n' : ' ');
	return 0;
}

让我们一起膜拜大佬林瑞堂