洛谷基础赛17「Diligent-OI R1 C」DlgtRank

很巧妙的数学题，思维题。

一开始的构造数组根本没有任何头绪，无从下手，于是来补题。

题目保证数组每个数字在一定的有限次变化后，最后都会达到全部可移动的状态，要求出每个数字达到可移动状态的最少次数。

经分析可以看出，最大一个数字本身可以达到可移动，因为最大数字前面没有更大数了，它不需要其他数字先进行操作，也就是说它第一次进行操作就能满足条件，先对它进行一次操作，然后再看第二个大的数字，它要最大的数字进行一次操作后才能满足条件，才变成可移动，然后第二轮里它变成可移动后可以加上k，第三大的数字也是一样，它需要等到最大的数字和次大数字变化后，它变成可移动，以此类推可以发现：每个数字变化次数确实是有限次，且次数呈每次+1的趋势

先对数组进行排序，让数组从大到小进行排序，然后依次枚举每个数字看它们的变化次数，最大数字要变化n次，因为有n个数字要变化，假设有两个数字一共，那么第一轮是最大数字是可移动的它加k，然后使第二大数字变成可移动，然后第二大数字和第一大数字都会在第二轮+k，这才是真正的变化过程，不过不用担心这样的模拟最后答案会影响结果，我们会在记忆输出时统一处理，这里代码这样模拟只是为了好写，其实想想就可以知道，如果是正向的从最小数字开始每轮将它们加1然后去着重判断后半部分可移动的数字，或者采用还是从大到小的思路，但是每轮只是一次一次的加1这样两种思路都会增大时间复杂度，并且不好写。

回到解题思路上来，我们还需要一个数组保存下来增大x*k倍之后的数字，这样做的好处是我们判断后面数字需要加上几次k变化时是容易计算的，只需要用前一个数变化后的数字减掉当前数字再减掉k-1即可，为什么是这样奇怪的式子，是因为我们要保证排序后相邻两项的差大于k，这样才能保证它们两个一直处在可移动特性中，也就是上一个数字至少比当前数字大出k+1个数字才行，那么就是上一个变化后的数字减掉ai+k+1，然后整体除上k，就能知道本次数字该乘上几个k了。

特别的，如果该数字是第一个数字直接乘上n，如果不是第一个数字且该数字和上一个数字相等，那么直接用上一次的数字变换到的数字即可，都乘上相同的数字可以确保相对可移动性。

最后处理答案时用n减掉（变化后的数字减去变化前的数字）/ k，就是最后要变化的次数。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
long long n, k, pos[N], ans[N];
struct node{
    long long x, id;
}a[N];
bool cmp(node x, node y)
{
    return x.x > y.x;
}
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++ i )
    {
        cin >> a[i].x;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; ++ i )
    {
        if (a[i].x != a[i - 1].x)
        {
            if (i == 1 ) pos[i] = a[i].x + n * k;
            else pos[i]=a[i].x+min(n,(pos[i-1]-k-a[i].x-1)/k)*k;
        }
        else pos[i] = pos[i - 1];
        ans[a[i].id] = n - (pos[i] - a[i].x) / k;
    }
    for (int i = 1; i <= n; ++ i ) cout << ans[i] << ' ';
    return 0;
}

以上便是代码全部讲解