72. 字串变换

有点冗长。思路见node的构造。其他的就是具体的实现了。

include

include

include

include

using namespace std;

struct node
{
string s;
char min_s[100];
int arr_every[100];
};//s是输出的原串，min_s代表不改变次序的最小字符串，arr_every则记录min_s里每个字母出现的次数

int abs(int x)
{
return x>=0?x:-x;
}

void deal(node &p)
{
string ss=p.s;
int len=ss.length();
for(int i=0;i<len-1;i++){
if(ss[i]==ss[i+1])
ss[i]=‘0’;
}
for(int i=0;i<100;i++)
p.arr_every[i]=1;
int j=0;
for(int i=0;i<len;i++){
if(ss[i]==‘0’)
p.arr_every[j]++;
else{
p.min_s[j]=ss[i];
j++;
}
}
p.min_s[j]=’\0’;
}//由s获得min_s和arr_every

int search_mid(int arr[],int n)
{
sort(arr,arr+n);
return arr[n/2];
}

int main()
{
int n;
cin>>n;
node a[n];
for(int i=0;i>a[i].s;
deal(a[i]);
}
int flag=true;
for(int i=1;i<n;i++){
if(strcmp(a[i].min_s,a[0].min_s)!=0){
flag=false;
break;
}
}//判断不合法情况
if(!flag)
cout<<”-1”<<endl;
else{
int sum=0;
int m=strlen(a[0].min_s);
for(int i=0;i<m;i++){
int temp[n];//记录min_s中某个字母在所有原串各自出现的次数
for(int j=0;j<n;j++)
temp[j]=a[j].arr_every[i];
int mid=search_mid(temp,n);//找到字母改变次数最小的情况（即对应对应字母应该如何改变）
for(int j=0;j<n;j++){
if(a[j].arr_every[i]!=mid)
sum+=abs(a[j].arr_every[i]-mid);
}
}
cout<<sum<<endl;
}
return 0;
}

10sec只会暴力，附上愚笨的思路。之前有个队列变形，字符串变化之类的是用dp做的。但是这题的变换，不会新增新的字符，也不会删除原有的字符，并且不能改变字符的出现次序。因为用一个struct node把每个字符的记录下来。

include

include

include

include

using namespace std;
const int maxn = 100005;

struct node{
char c;
int n;
}temp;
vector A[maxn];
int n;
char ch[105];
vector vt;

void deal(char ch[],int index){
int len = strlen(ch);
int k = 0,num=0;
for(int i=0;i<len;i++){
int j = i+1;
while(ch[i]==ch[j]){
j++;
}
temp.c = ch[i];
temp.n = j-i;
i = j-1;
A[index].push_back(temp);
}
}

bool test(){
bool flag = true;
int i = 1;
while(i<n){
if(A[i].size() != A[i-1].size()){
flag = false;
break;
}
i++;
}
if(!flag){
return flag;
}
int len = A[0].size();
for(int j=0;j<len;j++){//第j个结点
int i = 1;
while(i<n){
if(A[i][j].c != A[i-1][j].c){
flag = false;
break;
}
i++;
}
if(!flag){
break;
}
}

return flag;

}

int cal(){
sort(vt.begin(),vt.end());
int ans = 0, ans1 = 0, ans2 = 0;
int len = vt.size();
int mid,mid1,mid2;
if(len%2==0){
mid1 = len/2-1;
for(int i=0;i<mid1;i++){
ans1 += vt[mid1]-vt[i];
}
for(int i=mid1;i<len;i++){
ans1 += vt[i] - vt[mid1];
}

    mid2 = len/2;
    for(int i=0;i<mid2;i++){
        ans2 += vt[mid2]-vt[i];
    }
    for(int i=mid2;i<len;i++){
        ans2 += vt[i] - vt[mid2];
    }
    ans = min(ans1,ans2);
    return ans;
}else{
    mid = len/2;
    for(int i=0;i<mid;i++){
        ans += vt[mid]-vt[i];
    }
    for(int i=mid;i<len;i++){
        ans += vt[i] - vt[mid];
    }
}

return ans;

}

int main(){
// freopen(“72.txt”,”r”,stdin);
scanf(“%d”, &n);
for(int i=0;i<n;i++){
scanf(“%s”, ch);
deal(ch,i);
}

int ans = 0; 
if(test()){
    int len = A[0].size();
    for(int j=0;j<len;j++){//第j个结点 
        vt.clear();
        for(int i=0;i<n;i++){//n个字符串
            vt.push_back(A[i][j].n);
        }
        ans += cal();
    }
    printf("%d\n", ans);
}else{
    printf("-1\n");
}   
return 0;

}