关于c++:解题-String-Transformation-1贪心

String Transformation 1（Codeforces 659 Div.2 C）

Codeforces的Div.2真是越来越难了QwQ

挂个链接先 – https://codeforces.com/contes/1384/problem/c

题面 – 一共若干组数据，每组数据蕴含A，B两个长度为N的由a~t组成的字符串，你能够抉择A串中任意几个雷同的字母减少它的ACSLL码，问起码多少次操作能够使其变为B串，无奈变成B串则输入-1

Now，开始解题

必定先瞧下数据，10*100000级别，那必定贪婪、DP(动静布局)、图论建模三选一

奢侈图论建模首当其冲的在工夫复杂度上挂掉了（官网题解是图论建模+贪婪+并查集(求连通块个数)，我也写了相干文章）

再说DP，无显著档次，可能会有后效性，也就在图论之后也挂掉了

那就只有贪婪了

先想到的是串转数后排序，再模拟题中的操作，这样就疏忽了地位，起初在笔者受同学的一种办法启发，想出了一种正确的贪婪并AC了这道题，上面将介绍这种贪婪办法

算法工夫复杂度 – O(Q*N)

核心思想 – 建表以体现状态的递进

首先，如何建表？建什么表？

笔者建的表是一个二维数组，体现的是同一下标的A与B的字母对应关系（实际上数量对后果没有影响，想想为什么）
a[i][j]寄存的就是有多少个A中的(‘a’+i-1)对应B中的(a+j-1)
比方a[1][2]=3示意有3个A中的’a’对应B中的’b’

举个残缺的栗子

开始贪婪的操作

按列扫描，对于每列，将这一整列移到与该该列第一个非零元素的下标雷同的列
还没懂的能够联合下相干程序

for(int k=j+1; k<=26; k++){
    if(a[k][j]>0){ //如果该元素非零 
        if(f==0){ //如果之前未有过非零元素 
            f=1; //标记 
            temp=k-j; //算出之后的元素要挪动的量 
        }
        else{ //否则之前有过 
            a[k][j+temp]++; //挪动  
}
            

贪婪这就完结了？！
没错，真的完结了……

这个贪婪看似漏洞百出，甚至笔者本人一开始都有所狐疑
这实际上无懈可击，没有任何谬误
在工夫复杂度上甚至优于官网给出的题解

最初照例奉上残缺程序(C++)和精心设计的注解

//CF #659 Div.2 C - String Transformation 1 
//https://codeforces.ml/contest/1384/problem/c
//贪婪  

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    
    int T;
    cin >> T;
    int a[21][21];
    
    for(int i=1; i<=T; i++){
        int N, ans=0;
        cin >> N;
        for(int j=1; j<=26; j++)
            for(int k=1; k<=26; k++)
                a[k][j]=0;
        string A, B;
        cin >> A >> B;
        int f=0;
        for(int j=0; j<N; j++){
            if(A[j]>B[j]){ //如果A内有元素大于B内所对应的 
                cout << -1 << endl; //输入-1 
                f=1; //标记 
                break;
            }
            if(A[j]<B[j])
                a[B[j]-'a'+1][A[j]-'a'+1]++; //否则填表 
        }
        if(f==1)
            continue;
        int temp;
        for(int j=1; j<=26; j++){
            f=0;
            for(int k=j+1; k<=26; k++){
                if(a[k][j]>0){ //如果该元素非零 
                    if(f==0){ //如果之前未有过非零元素 
                        f=1; //标记 
                        temp=k-j; //算出之后的元素要挪动的量 
                    }
                    else{ //否则之前有过 
                        a[k][j+temp]++; //挪动  
                    }
                }
            }
            if(f==1) //如果执行过操作 
                ans++; //操作总数++ 
        }
        cout << ans << endl;
    }
    
    return 0;
}