小红的孤独数

贪心解法：

我们可以知道，如果数组中所有的数字都不相同，那么就不用进行调整了。

如果数组里面有重复出现的数字，就需要操作这些数字，而且我们只需要操作重复的数字。

显然，我们调整的时候，应该从小到大进行调整，于是，考虑用贪心法。

具体方法是：

1. 对整个数组从小到大排序。

2. 使用两个数据结构，一个结构是集合 set，存储当前已经调整后的数。另外一个是 map<int,int>，map中任意一个 key 和value对的含义是：操作每个 key 的值的时候，操作了 value 次，最后它的值为 key + value* k, 随后我们将 key + value* k 放入到 set 中。

3. 用 ret 表示最终调整的总次数。

4. 依次遍历数组中的数，对于每个数(用 key 表示)，

   1. 如果 key 不存在与 set 中，说明不需要调整，直接插入到 set 中，并且记录其操作次数为 value = 0，放入 map 中。
   2. 如果 key 已经存在于 set 当中，那么说明这个值需要被调整。我们从 map 中寻找它上次被调整的次数 value，然后逐渐增加 value 的值进行调整，最后使得 key + value* k 的值不存在与 set 中，此时调整结束, 将 key + value* k 插入到 set 中。 最后更新 ret += value。

5. 最后的答案是3.2 步骤中所有数的操作次数之和。
   最终整个操作的时间复杂度有排序和调整两部分组成，其为：
   整个代码如下：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n, 0);
    unordered_set<int> us;
    for (auto& e : v)cin >> e;
    sort(v.begin(), v.end());
    unordered_map<int, int> umap;
    int64_t ret = 0;
    for (auto& e : v) {
        if (us.count(e) == 0) {
            us.insert(e);
            umap[e] = 0;
            continue;
        }
        int cnt = umap[e] + 1;
        while (us.count(cnt * k + e))
            cnt++;
        ret += cnt;
        umap[e] = cnt;
        us.insert(cnt * k + e);
    }
    std::cout << ret << std::endl;
}
// 64 位输出请用 printf("%lld")

/*
    很简单的一道题，使用一个哈希表来存储<数，最小不重复数需增加的次数t>.每次
    有新的数获取的时候，就需要查找这个数是否在哈希表中，如果有，那么就将原先的t+1，
    当前的数加上t+1.在设置一个count来统计当前数增加的次数。没有出现过的数t统一为0.
*/

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int n, k;
    cin>>n>>k;
    vector<int> nums(n, 0);
    unordered_map<int, int> ump; 
    long long ans = 0;
    for(int i = 0; i < n; ++i) {
        int num;
        cin>>num;
        while(ump.find(num) != ump.end()) {
            ump[num] += 1;
            ans += ump[num];
            num += ump[num] * k;
        }
        ump[num] = 0; 
    }
    cout << ans;
    return 0;
}
// 64 位输出请用 printf("%lld")

n, k = list(map(int, input().split()))

nums = list(map(int, input().split()))

num_dic = {}

for num in nums:
    if num not in num_dic:
        num_dic[num] = 0
    num_dic[num] += 1

res = 0
for num in list(num_dic.keys()):
    if num_dic[num] > 1:
        last_val = num
        last_res = 0
        while num_dic[num] > 1:
            val = last_val
            cur_res = last_res
            while val in num_dic.keys():
                cur_res += 1
                val += k
            num_dic[val] = 1
            num_dic[num] -= 1
            res += cur_res
            last_val = val
            last_res = cur_res
print(res)