题解 P1900 【自我数】

ghj1222 · 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;
}

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