首页 > 代码库 > poj1007【求逆序数】
poj1007【求逆序数】
Description
One measure of ``unsortedness‘‘ in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC‘‘, this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence ``AACEDGG‘‘ has only one inversion (E and D)---it is nearly sorted---while the sequence ``ZWQM‘‘ has 6 inversions (it is as unsorted as can be---exactly the reverse of sorted).
You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of ``sortedness‘‘, from ``most sorted‘‘ to ``least sorted‘‘. All the strings are of the same length.
You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of ``sortedness‘‘, from ``most sorted‘‘ to ``least sorted‘‘. All the strings are of the same length.
Input
The first line contains two integers: a positive integer n (0 < n <= 50) giving the length of the strings; and a positive integer m (0 < m <= 100) giving the number of strings. These are followed by m lines, each containing a string of length n.
Output
Output the list of input strings, arranged from ``most sorted‘‘ to ``least sorted‘‘. Since two strings can be equally sorted, then output them according to the orginal order.
Sample Input
10 6AACATGAAGGTTTTGGCCAATTTGGCCAAAGATCAGATTTCCCGGGGGGAATCGATGCAT
Sample Output
CCCGGGGGGAAACATGAAGGGATCAGATTTATCGATGCATTTTTGGCCAATTTGGCCAAA
分析：求逆序数
因为数据很小只有四个字母可以直接求也可用树状数组
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 105; 8 char str[maxn][55]; 9 int num[300];10 11 int n, m;12 int ans[10];13 int ord(int k) {14 int cnt = 0;15 for(int i = 0; i < n; i++) {16 int x = num[(int)str[k][i]];17 for(int j = 4; j > x; j--) {18 cnt += ans[j];19 }20 ans[x]++;21 }22 return cnt;23 }24 void init() {25 memset(ans, 0, sizeof(ans));26 num[(int)‘A‘] = 1;27 num[(int)‘C‘] = 2;28 num[(int)‘G‘] = 3;29 num[(int)‘T‘] = 4;30 }31 32 struct Node {33 int id;34 int num1;35 }node[maxn];36 37 bool cmp(Node n1, Node n2) {38 if(n1.num1 != n2.num1) return n1.num1 < n2.num1;39 return n1.id < n2.id;40 }41 42 43 int main() {44 init();45 while(EOF != scanf("%d %d",&n, &m) ) {46 for(int i = 0; i < m; i++) {47 scanf("\n%s", str[i]);48 }49 for(int i = 0; i < m; i++) {50 memset(ans, 0, sizeof(ans));51 node[i].id = i;52 node[i].num1 = ord(i);53 }54 sort(node, node + m, cmp);55 for(int i = 0; i < m;i++) {56 printf("%s\n", str[node[i].id]);57 }58 }59 return 0;60 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 int lowbit(int x) { 8 return x & ( - x ); 9 }10 11 int c[305];12 void Add(int x, int val) {13 while(x > 0) {14 c[x] += val;15 x -= lowbit(x);16 }17 }18 19 int Sum(int x) {20 int sum = 0;21 while(x <= 300) {22 sum += c[x];23 x += lowbit(x);24 }25 return sum;26 } 27 28 29 char str[105][55];30 struct Node {31 int id;32 int ord;33 }node[105];34 35 bool cmp(Node n1, Node n2) {36 if(n1.ord != n2.ord) return n1.ord < n2.ord;37 return n1.id < n2.id;38 }39 40 int main() {41 int n, m;42 while(EOF != scanf("%d %d",&n, &m) ) {43 for(int i = 0; i < m; i++) {44 scanf("\n%s", str[i]);45 memset(c, 0, sizeof(c));46 int sum = 0;47 for(int j = 0; j < n; j++) {48 sum += Sum(str[i][j]);49 sum -= c[str[i][j]];50 Add(str[i][j], 1);51 }52 node[i].id = i;53 node[i].ord = sum;54 }55 sort(node, node + m, cmp);56 for(int i = 0; i < m; i++) {57 printf("%s\n", str[node[i].id]);58 }59 }60 return 0;61 }
poj1007【求逆序数】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。