D. Zero Remainder Array

题目传送

题意：

给你一行数组，分别进行一下两种操作：

1. Choose exactly one i from 1 to n and increase ai by x (ai:=ai+x), then increase x by 1 (x:=x+1).
2. Just increase x by 1 (x:=x+1).

在给你一个k,求需要最小步骤的操作使元素中的每一个元素都能被k整除。

思路：

分别将数组里面的每一个元素摸k，在进行从大到小进行排序，这样能使每个元素到达k的步骤最少化，累加元素到k的差值，如果ai+1==ai则总步骤加上前一个的差值+k，这样能使每一个步骤数都不相同。

代码：

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=2e5+10;int t,n;ll a[N],b[N],ans,k;bool cmp(ll a,ll b){return a>b;}int main(){scanf(\"%d\",&t);while(t--){cin>>n>>k;memset(a,0,sizeof a);memset(b,0,sizeof b);for(int i=1;i<=n;i++){cin>>a[i];a[i]%=k;}sort(a+1,a+1+n,cmp);//从大到小进行排序ll ans=0;for(int i=1;i<=n;i++){if(a[i]==0)break;if(a[i]!=a[i-1])//不同就直接加上元素到k的步骤b[i]=k-a[i];else {b[i]=b[i-1]+k;//相同就直接加上前一个差值+k}ans=max(ans,b[i]+1);//+1是因为每次操作都是从2. Just increase x by 1 (x:=x+1).开始的。}printf(\"%lld\\n\",ans);}return 0;}