SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Polycarp wrote on the board a string s containing only lowercase Latin letters ('a'-'z'). This string is known for you and given in the input.

After that, he erased some letters from the string s, and he rewrote the remaining letters in any order. As a result, he got some new string t. You have to find it with some additional information.

Suppose that the string t has length m and the characters are numbered from left to right from 1 to m. You are given a sequence of m integers: b1,b2,…,bm, where bi is the sum of the distances |i−j| from the index i to all such indices jj that tj>ti (consider that 'a'<'b'<...<'z'). In other words, to calculate bi, Polycarp finds all such indices j that the index j contains a letter that is later in the alphabet than ti and sums all the values |i−j|.

For example, if t = "abzb", then:

• since t1='a', all other indices contain letters which are later in the alphabet, that is: b1=|1−2|+|1−3|+|1−4|=1+2+3=6;
• since t2='b', only the index j=3 contains the letter, which is later in the alphabet, that is: b2=|2−3|=1;
• since t3='z', then there are no indexes j such that tj>ti, thus b3=0;
• since t4='b', only the index j=3 contains the letter, which is later in the alphabet, that is: b4=|4−3|=1.

Thus, if t = "abzb", then b=[6,1,0,1].

Given the string s and the array b, find any possible string t for which the following two requirements are fulfilled simultaneously:

• t is obtained from ss by erasing some letters (possibly zero) and then writing the rest in any order;
• the array, constructed from the string tt according to the rules above, equals to the array b specified in the input data.

``` 1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <queue>
5 #include <string>
6 #include <vector>
7 #include <cmath>
8 #include <stack>
9 #include <map>
10
11 using namespace std;
12
13 #define ll long long
14 #define pb push_back
15 #define fi first
16 #define se second
17
18 const int N = 2e6 + 10;
19 int cnt[N];
20 int v[N];
21 int vis[N];
22 char t[N];
23
24 void solve()
25 {
26     int T;
27     cin >> T;
28     while(T--){
29
30         //个数清空
31         for(int i = 0; i <= 28; ++i) cnt[i] = 0;
32
33         string s;
34         cin >> s;
35         //统计每个字符的个数
36         for(auto ch : s){
37             cnt[ch - 'a']++;
38         }
39
40
41         int n;
42         cin >> n;
43         //权值
44         for(int i = 1; i <= n; ++i) cin >> v[i];
45         //已经填过
46         for(int i = 1; i <= n; ++i) vis[i] = false;
47
48         vector<int > zero_inx;
49         int len = 0;
50         //使用到哪个字符
51         int cnt_inx = 26;
52
53         while(len != n){
54             zero_inx.clear();
55             for(int i = 1; i <= n; ++i){
56                 if(vis[i] || v[i]) continue;
57                 zero_inx.pb(i);
58                 vis[i] = true;
59             }
60             int _size = zero_inx.size();
61             len += _size;
62             char ch;
63             for(int i = cnt_inx; i >= 0; --i){
64                 if(cnt[i] < _size) continue;
65                 ch = 'a' + i;
66                 cnt[i] = 0;
67                 cnt_inx = i;
68                 break;
69             }
70
71             //减去贡献的权值，填充字符
72             for(int i = 0; i < _size; ++i){
73                 t[zero_inx[i]] = ch;
74                 int d = 0;
75                 for(int j = zero_inx[i] + 1; j <= n; ++j) v[j] -= ++d;
76                 d = 0;
77                 for(int j = zero_inx[i] - 1; j >= 1; --j) v[j] -= ++d;
78             }
79         }
80         //cout << "====================" << endl;
81         for(int i = 1; i <= n; ++i) cout << t[i];
82         cout << endl;
83         //cout << "====================" << endl;
84     }
85
86 }
87
88 int main()
89 {
90     ios::sync_with_stdio(false);
91     cin.tie(0);
92     cout.tie(0);
93
94     solve();
95
96     return 0;
97 }```