主页 / 问题 / 1608772
Accepted
chu
Asked:2025-03-16 20:34:52 +0000 UTC2025-03-16 20:34:52 +0000 UTC

帮助减少最大值时的代码执行时间

  • 772
#include <iostream>
#include <vector>
#include <climits> 

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    int arr[20][10000];

    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> arr[i][j];
        }
    }
    int otjm = 0;
 
    for (int i = 0; i < k; ++i) {
       
        for (int j = 1; j < n; ++j) {
            int count = 0;
            for (int m = 0; m < j; ++m) {
                if (arr[i][m] > arr[i][j]) {
                    count++;
                }
            }
            otjm += count;
        }
    }

    cout << otjm;
   

    return 0;
}

（k - 行数最多 20，n - 列数最多 10000）

该程序的本质是，对于每一行中的每个数字，您需要找到左侧大于当前数字的数字数，然后将所有值相加。给出错误“超出最大值的时间限制”。如何优化？示例测试：

5 2

1 5 2 4 3

2 3 1 5 4

输出：7

c++

2 个回答

  1. Best Answer

    现在是时候使用合并排序来编写NlogN中的反转计算了。这是一个正常的情况merge_sort，但有一个特点：每当第二个数组中的元素“超越”第一个数组中的元素并插入到结果中时，“超越”元素的数量就会在反转计数器中累积。可以证明结果是数组所有元素的反转总次数。

    #include <iostream>
#include <vector>

using Array = std::vector<int>;

auto merge(const Array &a, const Array &b, Array &c) {
    size_t n_invs = 0;
    auto m = a.size();
    decltype(m) i = 0;
    auto n = b.size();
    decltype(n) j = 0;
    decltype(c.size()) k = 0;
    while (i < m && j < n) {
        if (a[i] <= b[j]) {
            c[k++] = a[i++];
        } else {
            c[k++] = b[j++];
            n_invs += m - i;
        }
    }
    for (; i < m; ++i) {
        c[k++] = a[i];
    }
    for (; j < n; ++j) {
        c[k++] = b[j];
    }
    return n_invs;
}

size_t merge_sort(Array &a) {
    auto i = a.size() >> 1;
    if (i == 0) {
        return 0;
    }
    Array lo(a.begin(), a.begin() + i         );
    Array hi(           a.begin() + i, a.end());
    auto n_invs = merge_sort(lo) + merge_sort(hi);
    return n_invs + merge(lo, hi, a);
}

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    std::cin >> n >> k;
    Array line(n);

    size_t answer = 0;
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> line[j];
        }
        answer += merge_sort(line);
    }
    std::cout << answer << '\n';
}
    • 2

  2. 另一个可能的解决方案：

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

int merge_sort(vector<int>& v, vector<int>& t, int left, int right) {
    if (left >= right) 
        return 0;
    
    int mid = (left + right) / 2;
    size_t inv = 0;
    inv += merge_sort(v, t, left, mid);
    inv += merge_sort(v, t, mid + 1, right);
    copy(v.begin() + left, v.begin() + right + 1, t.begin() + left);
    int li = left, ri = mid + 1;
    for (int i = left; i <= right; ++i) {
        if (li > mid) {
            v[i] = t[ri++];
            continue;
        }
        if (ri > right) {
            v[i] = t[li++];
            continue;
        }
        if (t[li] <= t[ri])
            v[i] = t[li++];
        else {
            v[i] = t[ri++];
            inv += mid - li + 1;
        }

    }
    return inv;
}

int main() {
        
int n, k;
cin >> n >> k;
            
vector<vector<int>> arr(k, vector<int>(n));
        
      for (int i = 0; i < k; ++i) {
           for (int j = 0; j < n; ++j) {
               cin >> arr[i][j];
           }
      }
            int c = 0;
            
            for (int i = 0; i < k; i++) {
                vector<int> time(n);

                c += merge_sort(arr[i], time, 0, n-1);
            }
    
        cout << c;
        return 0;
    }
    • 0

相关问题