[Codeforces 962D] Merge Equals

[Codeforces 962D] Merge Equals - 1600

문제 설명 : 

n개의 수로 이루어진 수열이 주어진다. 이 수열에서 가장 작으면서 같은 값 2개를 합쳐서 그 수의 합으로 merge하는 연산이 가능하고, 그 결과 값은 두 수 중에서 오른쪽에 있던 수의 위치에 채워지게 된다(왼쪽에 있던 값은 사라진다). 가능한 모든 merge연산을 마친 뒤의 수열의 결과를 구하는 문제이다.

풀이 : 

stl로 떡칠하면 풀기 수월한 문제이다.

일단 n이 최대 15만이므로 O(N^2)안에 풀어야 한다. 따라서 merge연산을 한 번 할 때마다 합친 다음에 다시 처음부터 수를 살펴볼 여유가 없다. 처음부터 모든 수를 저장해놓은 다음에 조건이 맞으면 그때그때 merge를 해야한다. 그래서 처음에 set< pair<ll,ll> > (ll은 long long type)을 만들어두고 그 안에 pair의 first로는 원소의 값, second로는 원소의 인덱스를 저장해놓는다. 그리고 while문 안에서 merge연산이 가능할 때까지 계속 수행할 것이다. merge연산 가능 판단 여부는 set에서 맨 앞(가장 값이 작은 원소)와 그 다음(next)원소의 값이 같은지 확인하고, 같다면 next의 second에 저장하면 되는 것이다. merge한 뒤에는 두 원소를 삭제하고 새로운 원소는 별도의 ans vector에 넣어준다. 이 연산을 set이 빌 때까지 계속 해주면 된다.

이 풀이는 pair<first,second>의 대소 판단 기준이 first가 오름차순, first가 같다면 second 오름차순이 디폴트로 설정되어있다는 것을 전제하기 때문에 가능한 풀이이다. 그러므로 처음에 set에 저장이 될 때에도 first가 작은 순, 즉 원소의 값이 작은 순으로 먼저 저장이 되고 원소의 값이 같다면 인덱스가 작은 순으로 저장이 된다. 따라서 set의 iterator에서 begin부터 보면 되는 것이고 새로운 값은 next의 second(인덱스)에 저장하는 것이다.

주의할 점 : 

-

배운 점 : 

처음에 모든 원소를 set에 집어넣은 뒤에 here와 next를 비교하면서 값이 같으면 merge해주면 된다. 확실히 set이나 map의 템플릿으로 pair를 넣으면 신기한 일들이 많이 벌어진다.

코드 :

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b){
        a=_a;
        b=_b;
    }
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 150009;
set<pll> sll;
bool cmp(pll &A, pll &B){
    return A.second<B.second;
}
int main(){
    int n;    scanf("%d",&n);
    for(int i=1 ; i<=n ; i++){
        int inp;    scanf("%d",&inp);
        sll.insert({(ll)inp,(ll)i});
    }
    vector<pll> ans;
    while(!sll.empty()){
        auto here=sll.begin();
        ll cur_fir=here->first,cur_sec=here->second;
        auto next=++here;
        ll next_fir=next->first,next_sec=next->second;
        if(cur_fir==next_fir){
            sll.erase(sll.begin());
            sll.erase(sll.begin());
            sll.insert({cur_fir*2,next_sec});
        }    
        else{
            sll.erase(sll.begin());
            ans.push_back({cur_fir,cur_sec});
        }
    }
    sort(ans.begin(),ans.end(),cmp);
    printf("%d\n",ans.size());
    for(auto here:ans){
        printf("%lld ",here.first);
    }
    return 0;
}