题意
给一个字符串\(t\),和一个长度为\(m\)的数组\(b[]\),要求构造一个字符串\(s\),\(s\)中的字符都出现在\(t\)中,对于\(s[i]\)而言,对于任意\(j\),如果有\(s[i]<s[j]\),则\(\sum abs(i-j)=b[i]\),即\(i\)到所有比\(s[i]\)大的下标距离之和等于\(b[i]\)
分析
字符串\(t\)提供的就是每个字符的数量,我们发现对于字符最大的位置,\(b[i]\)肯定为\(0\),然后次大的位置,\(b[i]\)被这些最大的位置影响,以此类推,我们保存一个已经填进去的数组,然后每一次枚举的时候将这个位置与数组中的数求绝对值之和,因为已经填进去的字符肯定比当前位置字符要大,所以如果这个和等于\(b[i]\),则这个数这一轮是可以填的,然后就是从大到小枚举字符,如果字符数比当前填的个数大,则选择,否则选小的字符
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 3e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;
char s[maxn];
int a[maxn];
int num[maxn];
char ans[maxn];
bool vis[maxn];
void solve() {
int n;
cin >> (s + 1) >> n;
rep(i, 1, n)cin >> a[i], vis[i] = false;
rep(i, 0, 26)num[i] = 0;
rep(i, 1, strlen(s + 1))++num[s[i] - 'a'];
vector<int> v;
int m = n;
int now = 25;
while (m > 0) {
int tot = 0;
vector<int> pos;
rep(i, 1, n) {
if (vis[i])
continue;
int sum = 0;
for (auto &to:v)
sum += abs(to - i);
if (sum == a[i])
pos.push_back(i);
}
for (auto &to:pos) {
vis[to] = true;
++tot;
v.push_back(to);
}
while (num[now] < tot)
--now;
m -= tot;
for (auto &to:pos)
ans[to] = (char) (now + 'a');
--now;
}
rep(i, 1, n)cout << ans[i];
cout << '\n';
}
signed main() {
start;
cin >> T;
while (T--)
solve();
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章