题解 | #追求女神#

c题题解，将x化为pk+b的形式。按照k进行分组，然后用map统计每组的数量。然后根据k的移动，确定index的最后三次排序得出结果

#include<bits/stdc++.h>
using namespace std;
#define ll long long
map<ll,ll> num;
ll ss[10000100];
int main()
{
    ll n,k,p;
    ll maxs=-9223372036854775808;
    scanf("%lld%lld%lld",&n,&k,&p);

    for(ll i=0;i<n;i++)
    {
        ll x,s;
        scanf("%lld",&x);
        ss[i]=x;
        if(p!=0)
            s=x/p;//把x化为ps+b处理
        maxs=max(s,maxs);
        num[s]++;
    }
    if(p==0)
    {
        sort(ss,ss+n);
        for(ll i=0;i<n;i++)
        {
            printf("%lld",ss[i]);
            if(i==n-1)
                printf("\n");
            else
                printf(" ");
        }
        return 0;
    }
    ll index=maxs;
    ll last=0;
    while(1)
    {
        if(k>num[index])
        {
            k=k-num[index];
            num[index-1]+=num[index];
            last=num[index];
            num.erase(index);
            index--;//
        }
        else
            break;
    }
    sort(ss,ss+n);
    ll fir=lower_bound(ss, ss+n, index*p)-ss;
    fir=fir+num[index]-k-1;
    for(ll i=n-last;i<n;i++)
    {
        ss[i]=ss[i]%p+(index)*p;
    }
    sort(ss,ss+n);
    for(ll i=n-1;i>=n-k;i--)
    {
        ss[i]-=p;
    }
    sort(ss,ss+n);
    for(ll i=0;i<n;i++)
    {
        printf("%lld",ss[i]);
        if(i==n-1)
            printf("\n");
        else
            printf(" ");
    }
    return 0;
}