题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

const int N = 210, k = 210;
int n, m;

void mergesort(vector<int>& line, int l, int r, int& t)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    mergesort(line, l, mid, t);
    mergesort(line, mid + 1, r, t);
    vector<int> tmp;
    for (int i = l, j = mid + 1; i <= mid || j <= r;)
    {
        if (i > mid) tmp.push_back(line[j ++]);
        else if (j > r)
        {

            tmp.push_back(line[i ++]);
        }
        else if (line[i] <= line[j]) tmp.push_back(line[i ++]);
        else if (line[i] > line[j])
        {
            t += mid - i + 1;
            tmp.push_back(line[j ++]);
        }
    }
    for (int i = l, k = 0; i <= r; i ++, k ++) line[i] = tmp[k];
}

int main()
{
    cin >> n >> m;

    map<pair<int, int>, vector<int> > memo;//维护顺序；

    for (int i = 0; i < n; i ++)
    {
        vector<int> line;
        for (int j = 0; j < m; j ++)
        {
            int x;
            cin >> x;
            line.push_back(x);
        }
        auto nline = line;
        int t = 0;
        mergesort(nline, 0, m - 1, t);
        memo[{t, i}] = line;
    }

    int k = 0;
    cout << "[";
    for(auto line : memo)
    {
        if (k == 0) cout <<"[";
        else cout << ", [";
        for (int i = 0; i < line.second.size(); i ++)
        {
            if (i == 0) cout << line.second[i];
            else cout << ", " << line.second[i];
        }
        cout << "]";
        k ++;
    }
    cout << "]";
    return 0;

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 200;

int a[N][N], cnt[N], index[N];
int n, m;

bool cmp(int a, int b)
{
    int x = cnt[a], y = cnt[b];
    if (x != y) return x < y;
    return a < b;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
            cin >> a[i][j];

        for (int l = 0; l < m; l ++)
            for (int r = l + 1; r < m; r ++)
                if (a[i][l] > a[i][r]) cnt[i] ++;

        index[i] = i;
    }

    stable_sort(index, index + n, cmp);

    cout << "[";
    for (int i = 0; i < n; i ++)
    {
        if (i == 0) cout << "[";
        else cout << ", [";
        for (int j = 0; j < m; j ++)
        {
            if (j == 0) cout << a[index[i]][j];
            else cout << ", " << a[index[i]][j];
        }
        cout << "]";
    }
    cout << "]";
    return 0;

}