[Codeforces][Round #650][Div.3] D : Task On The Board (C++)

https://codeforces.com/contest/1367/problem/D

Problem - D - Codeforces

 

 

[난이도] Div.3
[유형] Greedy

[풀이]
b[i]가 0인 i에는 가장 큰 알파벳이 있다는 것을 문제의 조건을 통해 알 수 있다.
(더해줄 abs(i-j)가 없으므로).
1. 현재 배열 상태에서 b[i]가 0인 i들을 찾고 그곳에 사용할 수 있는 알파벳중 큰 순서대로 확인하면서
찾은 0의 개수보다 알파벳 개수가 크거나 같으면 그 알파벳으로 찾은 i위치에 할당한다.
2. 위에서 찾은 인덱스들은 다른 b[i]들에 영향을 주면 안되므로 거리만큼 빼줘서 영향을 제거해준다.

위 과정을 반복해서 m개를 모두 찾으면 정답 스트링을 출력한다.

 

#include <string>
#include <queue>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
int tc,n,k,b[51],cnt[27];
int main(){
    scanf("%d",&tc);
    while(tc--){
        string s;
        cin >> s >> n;
        for(int i=0;i<n;i++) cin >> b[i];
        priority_queue<int> q;
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<s.size();i++){
            if(!cnt[s[i]-'a']) q.push(s[i]-'a');
            cnt[s[i]-'a']++;
        }
        string ans;
        ans.resize(n);
        int total=0;
        while(total<n){
            vector<int> t;
            for(int i=0;i<n;i++) {
                if(b[i]==0) {
                    b[i]=-1;
                    t.push_back(i);
                }
            }
            for(int i=0;i<n;i++) {
                if(b[i]==-1) continue; 
                for(auto k : t) b[i]-=abs(i-k);
            }
            while(!q.empty()){
                if(cnt[q.top()]>=t.size()){
                    for(auto k : t) ans[k]=q.top()+'a';
                    q.pop();
                    total+=t.size();
                    break;
                }
                q.pop();
            }
        }
        cout << ans << '\n';
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round650-Div.3/D.cpp