乐趣区

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

jiezi

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;
}
退出移动版