codeforces 1367D（思维）

题意描述

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 j 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 s by erasing some letters (possibly zero) and then writing the rest in any order; the array, constructed from the string t according to the rules above, equals to the array b specified in the input data.

思路

可以发现，如果某一位的数字为0，则说明该位所对应的字母是最大的。找到最大的字母后，再计算该字母对于所有其他字母的贡献，接着一定又用某位数字为0，重复该过程即可。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define ins(x) inserter(x,x.begin())
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=4*1e5+10;
const int M=1e6+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
int cnt[26],b[55];
bool vis[55];
void solve(){
    mst(vis,0);
    mst(cnt,0);
    string s;cin>>s;
    string ans=s;
    int n;cin>>n;
    vector<int> v;
    rep(i,0,n) cin>>b[i];
    rep(i,0,s.size()) cnt[s[i]-'a']++;
    int m=n;
    int now=25;
    while(m>0){
        int tot=0;
        vector<int> pos;
        //统计贡献，并且统计和该贡献相同的字母
        rep(i,0,n){
            if(vis[i]) continue;
            int sum=0;
            rep(j,0,v.size()) sum+=abs(v[j]-i);
            if(sum==b[i]) pos.PB(i);
        }
        //方便下次循环贡献的计算
        rep(i,0,pos.size()){
            vis[pos[i]]=true;
            tot++;
            v.PB(pos[i]);
        }
        //找到和tot出现次数相同的最大字母
        while(cnt[now]<tot) now--;
        m-=tot;
        rep(i,0,pos.size()){
            ans[pos[i]]=(char)(now+'a');
        }
        now--;
    }
    rep(i,0,n) cout<<ans[i];
    cout<<endl;
}
int main(){
    IOS;
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}