用c++写 一个排列，求出了 a 数组，其中 ai 表示第 i个数左边有多少个数比它小。 计算出原来的排列。 输入 第一行输入 n 接下来 n - 1 个整数 ai，下标从 2开始。 1<=n<=100000 输出 输出 n 个整数表示原排列。

没问题，这是一个典型的线性时间复杂度排序算法，可以使用计数排序或归并排序完成。

以下是计数排序的示例代码：

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n, i, count[100001] = {0};
    scanf("%d", &n);
    for (i = 2; i <= n; i++) {
        int a;
        scanf("%d", &a);
        count[i] = count[i - 1] + a;
    }
    int *a = (int *) malloc(sizeof(int) * n);
    for (i = 1; i <= n; i++) {
        a[count[i]] = i;
        count[i]++;
    }
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
    return 0;
}

这段代码可以读入 n 和 ai，然后使用计数排序算法求出原排列，并输出结果。

接下来，您有其他问题需要回答吗？

相关问题

2 个长度 n （n<=100000）数组 a,b; 所有的 ai + bj 从小到大排序后输出第 l 到第 r 项 输入第一行 n,l,r 第二行 n 个整数是 a 数组 。第三行 n 个整数是 b 数组 。 输出排序后第 l 到第 r 个数 完整的c++代码

为了实现这个功能，我们可以使用优先队列（通常用`std::priority_queue`或`std::vector`和`std::sort`配合）来存储计算结果并保证它们按照升序排列。这里是一个简单的C++代码示例：

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

// 假设我们定义一个辅助结构PairWithIndex用于存储计算结果和对应的索引
struct PairWithIndex {
    int sum;
    int index;
    bool operator<(const PairWithIndex& other) const { return sum < other.sum; }
};

int main() {
    int n, l, r;
    std::cin >> n >> l >> r;

    // 读取数组a和b
    std::vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
    }

    // 计算所有可能的和并将它们存入优先队列
    std::priority_queue<PairWithIndex> pq;
    for (int i = 0; i < n; ++i) {
        pq.push({a[i] + b[i], i});
    }

    // 提取并打印第l到r个最小的和
    std::vector<PairWithIndex> sorted_results(l - 1);
    for (int i = 0; i < l - 1 && !pq.empty(); ++i) {
        sorted_results[i] = pq.top();
        pq.pop();
    }

    while (!pq.empty() && r > 0) {
        if (pq.top().index != sorted_results[r - 1].index) {
            sorted_results[r - 1] = pq.top();
            --r;
        } else {
            pq.pop();
        }
    }

    // 输出结果
    for (const auto& result : sorted_results) {
        std::cout << result.sum << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个代码中，我们首先创建了一个优先队列`pq`来保存所有的和，并使用`operator<`确保它们按升序排列。然后我们从队列中取出前`l - 1`个元素放入结果向量`sorted_results`。接着，我们检查当前队列中的元素是否小于我们需要的第`r`个元素，如果是，我们就把该元素添加到结果中并减少`r`。当`r`变为0时，队列中剩余的元素都是大于等于所需的，所以无需再处理。

Mihai和Bianca正在玩糖果袋游戏。他们有n个糖果袋排成一行。第i个糖果袋里有ai颗糖果。这些糖果袋按顺序从第一个到第n个给玩家。 如果一个糖果袋里有偶数颗糖果，那么Mihai抢夺这个糖果袋，否则，Bianca抢夺这个糖果袋。一旦一个糖果袋被抢夺，里面的糖果数量就会加到抢夺者的总糖果数量中。 Mihai想炫耀自己，所以他想重新排列这个数组，使得在任何时候（除了一开始他们都没有糖果的情况下），Mihai拥有的糖果数量严格大于Bianca。帮助Mihai判断是否存在这样的重新排列。 输入： 第一行包含一个整数t (1≤t≤1000) —— 测试用例的数量。 对于每个测试用例，第一行包含一个整数n (1≤n≤100) —— 数组中糖果袋的数量。 第二行包含n个用空格分隔的整数ai(1≤ai≤100) —— 每个糖果袋中的糖果数量。 输出： 对于每个测试用例，如果存在这样的重新排列，则输出“YES”（不含引号），否则输出“NO”（不含引号）。 答案不区分大小写（例如，字符串“yEs”，“yes”，“Yes”和“YES”将被视为肯定的答案）。写出c++代码

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[n];
        int sum = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            sum += a[i];
            if (a[i] % 2 == 0) cnt++;
        }
        if (cnt == 0 || (n % 2 == 0 && cnt == n)) { // 无偶数或全是偶数，无法满足条件
            cout << "NO" << endl;
            continue;
        }
        sort(a, a + n); // 排序
        int miaow = 0, bianca = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (a[i] % 2 == 0) { // 偶数
                miaow += a[i];
                i--;
            }
            if (miaow > bianca) { // 猫咪领先
                bianca += a[i];
            } else { // 猫咪不领先
                miaow += a[i];
            }
        }
        if (miaow > bianca) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}