http://poj.org/problem?id=1007 (题目链接)
题意
给出m个字符串,将其按照逆序对个数递增输出。
Solution
树状数组经典应用。
代码
// poj1007 #include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #include<string> #include<map> #define MOD 1000000007 #define inf 2147483640 #define LL long long #define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout); using namespace std; inline LL getint() { LL x=0,f=1;char ch=getchar(); while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=200; struct data {int cnt;char s[110];}a[maxn]; int n,m,c[10]; bool cmp(data a,data b) {return a.cnt<b.cnt;} int lowbit(int x) {return x&-x;} void add(int x) { for (int i=x;i<=4;i+=lowbit(i)) c[i]++; } int query(int x) { int s=0; for (int i=x;i>=1;i-=lowbit(i)) s+=c[i]; return s; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) scanf("%s",a[i].s); for (int i=1;i<=m;i++) { for (int j=0;j<=5;j++) c[j]=0; for (int j=n-1;j>=0;j--) { int x; if (a[i].s[j]=='A') x=1; else if (a[i].s[j]=='C') x=2; else if (a[i].s[j]=='G') x=3; else x=4; add(x); if (x>1) a[i].cnt+=query(x-1); } } sort(a+1,a+1+m,cmp); for (int i=1;i<=m;i++) printf("%s ",a[i].s); return 0; }