C++11(clang++ 3.9) 解法, 执行用时: 65ms, 内存消耗: 620K, 提交时间: 2020-03-18 15:47:10

#include<bits/stdc++.h>
using namespace std;

char R[200005],T[4]={'A','C','G','T'};
long long i,ans=2e18,s,a,b,c;
int main()
{
	scanf("%s",R);
	do
	{
        for(a=b=c=s=i=0;R[i]!='\0';i++)
		{
            if(R[i]==T[3]||R[i]==T[2]||R[i]==T[1])a++;
            if(R[i]==T[3]||R[i]==T[2])b++;
            if(R[i]==T[3])c++;
            if(R[i]==T[0])s+=a;
            if(R[i]==T[1])s+=b;
            if(R[i]==T[2])s+=c;
        }
        ans=min(ans,s);
    }while(next_permutation(T,T+4));
	printf("%lld\n",ans);
}

C++14(g++5.4) 解法, 执行用时: 120ms, 内存消耗: 8648K, 提交时间: 2020-01-13 17:33:26

#include<bits/stdc++.h>
using namespace std;
char s[200010];
map<char,int> mmp;
int flag[2000010];
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	int a[]={0,1,2,3,4};
	long long Min=LONG_LONG_MAX;
	while(next_permutation(a+1,a+4+1)){
		memset(flag,0,sizeof flag);
		mmp['A']=a[1],mmp['T']=a[2],mmp['G']=a[3],mmp['C']=a[4];
		long long ans=0;
		for(int i=1;i<=n;++i){
			for(int j=mmp[s[i]]+1;j<=4;++j){
				ans+=flag[j];
			}
			flag[mmp[s[i]]]++;
		}
		Min=min(ans,Min);
	}
	cout<<Min<<endl;
	return 0;
}