c/c++语言开发共享【题解】Building Strings Gym – 102152E

【题面】

you are given a string s of length n consisting of lowercase english letters. this string can be used to build other strings. the cost of each letter in s is given by another string c of length n consisting of digits, such that the cost of using the letter si is ci coins.

also, you are given another string p of length m consisting of unique lowercase english letters. your task is to find the minimum cost to build string p by using the letters of s. can you?

input
the first line contains an integer t (1≤t≤500) specifying the number of test cases.

the first line of each test case contains two integers n and m (1≤n≤103,1≤m≤26), in which n is the length of strings s and c, and m is the length of string p.

then 3 lines follow, each line contains a string, giving the string s, c, and p, respectively. both strings s and p contains only lowercase english letters, while string c contains only digits. also, string p is consisting of unique letters.

output
for each test case, print a single line containing the minimum cost of building the string p by using the letters of string s. if string p cannot be built using string s, print −1.

example
input
3
4 2
abcd
1234
ac
4 4
abcd
1234
abec
5 3
abcba
24513
acb
output
4
-1
8
note
in the first test case, you have to use the 1st and 3rd letters of string s to build string p. so, the total cost is 1+3=4.

in the second test case, you cannot build string p using s because the letter ‘e’ from p does not exist in s. so, the answer is −1.

in the third test case, the optimal way is to use the 1st, 3rd, and 4th letters of string s to build p. so, the total cost is 2+5+1=8.
【ac代码】

#include<iostream> #include<cstdio> #include<cstring> using namespace std;  char a[1005]; char str[1005]; char b[1000]; int main() { int t, n, m, i, j, k; scanf("%d", &t); while (t--) { int t[1005]; memset(t, -1, sizeof(t)); scanf("%d%d", &n, &m); scanf("%s", str); scanf("%s", a); for (i = 0; i < n; i++) { if (t[str[i]] > a[i]-'0'||t[str[i]]==-1) t[str[i]] = a[i]-'0'; } int ans = 0; scanf("%s", b); int flag = 0; for (i = 0; i < strlen(b); i++) { if (t[b[i]] == -1) { flag = 1; break; } ans += t[b[i]]; } if (flag) printf("-1n"); else printf("%dn", ans); } return 0; }

【心得】

c++数组的下标可以是字符的。

解释如下：

1. c++中字符在计算机内存储的是字符的ascii码；

2. 而ascii码实质是数字，例如‘a’是97,‘a’是65；

3. 如果用字符作为下标，实质就是用该字符的ascii码作为下标；

4. 但是在用字符作为下标时没有数字直观，容易引起数组越界，因此不建议这样用。