【POJ-1007】DNA Sorting【树状数组求逆序对】

【POJ-1007】DNA Sorting【树状数组求逆序对】

问题链接:https://vjudge.net/problem/POJ-1007

Solution:

使用树状数组求解逆序对,倒序遍历序列,树状数组记录到遍历当前位置出现的所有元素各自的数量【我们将’A’通过’A’ – ‘A’ + 2映射到2,其余字符都是CH – ‘A’ + 2】,对于每个序列中的元素,我们先查询遍历到当前位置出现过多少比它小的元素,每一个计数将代表有一个逆序对,之后将树状数组中当前元素的计数加1.

这道题要求对所有字符串进行逆序对数量从小到大排序,之后输出,使用结构体存放string和计数,并使用计数来排序就好了。

时间复杂度\(O(mnlogn)\).

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int LIM = 30;
int bitree[LIM];

void update(int pos) {
    for (; pos < LIM; pos += pos & (-pos))
        bitree[pos]++;
}

int query(int pos) {
    int ret = 0;
    for (; pos > 0; pos -= pos & (-pos))
        ret += bitree[pos];
    return ret;
}

struct Node {
    string str;
    int cnt;
    bool operator < (const Node &n) const {
        return cnt < n.cnt;
    }
};
vector<Node> dat;

int main(void) {
    ios::sync_with_stdio(false);
    // cin.tie(NULL);
    int n, m;
    Node tmp;
    while (cin >> n >> m) {
        dat.clear();
        for (int i = 0; i < m; i++) {
            cin >> tmp.str;
            tmp.cnt = 0;
            memset(bitree, 0, sizeof bitree);
            for (int j = n - 1; j >= 0; j--) {
                tmp.cnt += query(tmp.str[j] - 'A' + 1);
                // cout << query(tmp.str[j] - 'A' + 1) << endl;
                update(tmp.str[j] - 'A' + 2);
            }
            dat.push_back(tmp);
        }
        sort(dat.begin(), dat.end());
        for (int i = 0; i < m; i++) {
            cout << dat[i].str << '\n';
            // cout << dat[i].cnt << '\n';
        }
    }
    return 0;
}