题解：P11273 「Diligent-OI R1 C」DlgtRank
P11273题解
传送门
题意简述
给定长为n的序列，每次操作将序列中满足a_i + k 小于 a_j (a_j>a_i) 加上 k
求出每个数有几次不能加 k
解题思路
举个例子，变化形态如下（1为最开始的） k=2
- 3 8 10 12 16 19
- 5 8 10 14 18 21
- 7 8 12 16 20 23
- 7 10 14 18 22 25
- 后面全部都可以动故不给出
观察看到每次不能加
k 的位置（1为不加，0为加k ）- 0 1 1 0 0 0
- 0 1 0 0 0 0
- 1 0 0 0 0 0
结果：1 2 1 0 0 0
可观察到如果该位上最初不可加 k 那么该位等待次数等于上一位次数+1
如果该位最初可加 k 那么该位等待次数等于上一位等待次数减去加 k 小于上一位+1（给自己预留一个位置）
代码部分
#include<bits/stdc++.h>
using namespace std;
int in()//快读,后来发现scanf就够用了
{
int k=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
return k*f;
}
struct asd{
int op;
int w;
int ans;
};
asd num[1000600];
bool cmp(asd a,asd b){
return a.w>b.w;
}
int ans[1000600];
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>num[i].w;
num[i].op=i;
}
sort(num+1,num+1+n,cmp);
num[1].ans=0;
for(int i=1;i<=n;i++){
//cout<<num[i].w<<" ";
if(i==1){ //处理最大的数
num[i].ans=0;
continue;
}
if(num[i].w==num[i-1].w){//处理相等的数
num[i].ans=num[i-1].ans;
}
else if(num[i-1].w-num[i].w<=k){//如果这里最开始不能加，
// 那么这里等待次数为上一位+1
num[i].ans=num[i-1].ans+1;
}
else{//如果最开始可以相加，那么这里可以等待上一位的次数为上一位
//与这一位的差-1除k在加上一次（给自己预留一次空间）;
num[i].ans=max(0,num[i-1].ans-((num[i-1].w-num[i].w-1)/k-1));
}
}
for(int i=1;i<=n;i++){
ans[num[i].op]=num[i].ans;
}//按照输入顺序输出
for(int i=1;i<=n;i++){
printf("%d ",ans[i]);
}
return 0;
}