有一个序列 a 长度为 n. 可以选择序列中两个数字 ai 和 aj （i != j, 1 <= i, j <= n） 如果 ai = aj 将其中一个数更改为 0. 否则，将它们都更改为它们之中最小的数。 需要将序列中的数字都更改为 0. 请你求出最小操作次数。

对于这个问题，我们可以先统计序列中每个数出现的次数。然后对于相同的两个数，我们可以将其中一个数更改为 0，操作次数加 1。对于不同的两个数，我们将它们都更改为它们之中最小的数，操作次数也加 1。最后，我们只需要将所有数都更改为 0，操作次数再加上序列中不同的数的个数即可。

以下是具体实现的伪代码：

count = {}
distinct = 0
for i in range(n):
    if a[i] in count:
        count[a[i]] += 1
    else:
        count[a[i]] = 1
        distinct += 1

ans = 0
for k, v in count.items():
    if v > 1:
        ans += 1
    distinct -= 1

ans += distinct

其中 count 用于统计每个数出现的次数，distinct 表示不同的数的个数，ans 表示操作次数。

相关问题

c++代码 给定一个长度为n(n<=1e5)的序列a和一个整数k(k<=1e5)，请对于每个1<=i<=n，求出对应的1<=j<=n，使得ai异或aj第k大。 你需要输出这aj的值。

这是一个比较典型的异或问题，可以使用字典树来解决。具体思路如下：

1. 预处理出数组中任意两个数异或的结果，并将这些结果插入到字典树中。

2. 对于每个数a[i]，在字典树中查找异或结果中第k大的数，即可得到对应的aj的值。

以下是对应的C++代码实现：

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

const int N = 1e5 + 10;

int n, k, tot;
int a[N], trie[N * 30][2], cnt[N * 30];

void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (!trie[p][u]) trie[p][u] = ++tot;
        p = trie[p][u];
        cnt[p]++;
    }
}

int query(int x) {
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1, v = k >> i & 1;
        if (v) {
            if (trie[p][u ^ 1] && cnt[trie[p][u ^ 1]] >= v) {
                p = trie[p][u ^ 1];
                res |= (u ^ 1) << i;
            } else {
                p = trie[p][u];
                res |= u << i;
            }
        } else {
            if (trie[p][u] && cnt[trie[p][u]] >= v) {
                p = trie[p][u];
                res |= u << i;
            } else {
                p = trie[p][u ^ 1];
                res |= (u ^ 1) << i;
            }
        }
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        insert(a[i]);
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", query(a[i]));
    }
    return 0;
}

时间复杂度为O(nlogk)。

C++代码 给定一个长度为n（n<=1e5）的序列a和一个整数k（k<=1e5），请对于每个1<=i<=n，求出对应的1<=j<=n，使得ai异或aj第k大。你需要输出这aj的值。输入6 2 1 1 4 5 1 4 输出5 5 5 4 5 5

这是一个比较典型的异或问题，可以使用字典树来解决。具体思路如下：

1. 预处理出数组中任意两个数异或的结果，并将这些结果插入到字典树中。

2. 对于每个数a[i]，在字典树中查找异或结果中第k大的数，即可得到对应的aj的值。

以下是对应的C++代码实现：

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

const int N = 1e5 + 10;

int n, k, tot;
int a[N], trie[N * 30][2], cnt[N * 30];

void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (!trie[p][u]) trie[p][u] = ++tot;
        p = trie[p][u];
        cnt[p]++;
    }
}

int query(int x) {
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1, v = k >> i & 1;
        if (v) {
            if (trie[p][u ^ 1] && cnt[trie[p][u ^ 1]] >= v) {
                p = trie[p][u ^ 1];
                res |= (u ^ 1) << i;
            } else {
                p = trie[p][u];
                res |= u << i;
            }
        } else {
            if (trie[p][u] && cnt[trie[p][u]] >= v) {
                p = trie[p][u];
                res |= u << i;
            } else {
                p = trie[p][u ^ 1];
                res |= (u ^ 1) << i;
            }
        }
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        insert(a[i]);
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", query(a[i]));
    }
    return 0;
}

时间复杂度为O(nlogk)。