codeforces 962 D. Merge Equals

Description

You are given an array of positive integers. While there are at least two equal elements, we will perform the following operation. We choose the smallest value x that occurs in the array 2 or more times. Take the first two occurrences of x in this array (the two leftmost occurrences). Remove the left of these two occurrences, and the right one is replaced by the sum of this two values (that is, 2⋅$x$).

Determine how the array will look after described operations are performed.

For example, consider the given array looks like [3,4,1,2,2,1,1]
. It will be changed in the following way: [3,4,1,2,2,1,1] → [3,4,2,2,2,1] → [3,4,4,2,1] → [3,8,2,1].

If the given array is look like [1,1,3,1,1] it will be changed in the following way: [1,1,3,1,1] → [2,3,1,1] → [2,3,2] → [3,4].

Input

The first line contains a single integer n (2≤n≤150000) — the number of elements in the array.

The second line contains a sequence from n elements a$_1$,a$_2$,…,a$_n$ (1≤a$_i$≤10$^9$) — the elements of the array.

Output

In the first line print an integer $k$ — the number of elements in the array after all the performed operations. In the second line print $k$ integers — the elements of the array after all the performed operations.

Examples

Note

The first two examples were considered in the statement. In the third example all integers in the given array are distinct, so it will not change.

题意：每次选两个相同的数，它们是所有数中最小的而且是最左边的，把它们去掉并在原来第二个数的位置放上两数值的和（也就是原来的两倍），这样的操作能做几次？
分析：表面一看就是模拟题嘛，但是问题在与怎么高效做到在反复插入和删除的过程中，能迅速找到要删除的两个数，适合这种情况的数据结构就是优先队列啦。

• 定义

template < 
   class Type,  
   class Container=vector<Type>, 
   class Compare=less<typename Container::value_type>  
> 
class priority_queue

• 含义

  • Type
    
    • The element data type to be stored in the priority_queue.
  • Container
    
    • The type of the underlying container used to implement the priority_queue.
  • Compare
    
    • The type that provides a function object that can compare two element values as sort keys to determine their relative order in the priority_queue. This argument is optional and the binary predicate less < typename Container ::value_type > is the default value.

• 简单来说就是：第一个参数表示要存放的数据类型，第二个参数表示底层用那种容器来存放数据，第三个参数表示排序是升序还是降序的。

当向优先队列插入一个元素时，会被自动整理到有序的位置，我们可以利用这个性质，始终保证在队列前面是最小的两个数，这样每次只需要把这两个数取出来，$\times$2，再放回去就行了。

思路：建立<unsigned long long, int>型的数据类型，分别保存数值和所在位置，这样执行push后，优先队列将自动按数值和所在位置进行排序，我们只需要检查队列的前两个数是否相同：如果相同就取出$\times2$再放回去；如果不同，由于它是最小的数，那么一定没有数和它配对，直接把它取出来放到输出中。直到队列为空就结束。

代码：

#include<stdio.h>
#include<queue>
#include<vector>
#include<functional>
#include <algorithm>
using std::priority_queue;
using std::vector;
using std::greater;
using std::pair;
using std::sort;
typedef unsigned long long ll;
typedef pair<ll, int> P;

priority_queue<P,vector<P>,greater<P>> AC;
vector<P> opt;
bool cmp(P p1, P p2) {
    return p1.second < p2.second;
}
int main(){
    int n;
    ll a1;
    P next,temp;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%I64d", &a1);
        //以数值和位置构造一个P()插入优先队列
        AC.push(P(a1, i));
    }
    while (!AC.empty())
    {
        next = AC.top(); AC.pop();
        if ((!AC.empty())) {
            temp = AC.top();
            if (next.first == temp.first) {//有两个相同的数
                AC.pop();
                temp.first *= 2;
                AC.push(temp);
                continue;
            }
        }
     opt.emplace_back(next);//队列只剩一个，或者没有数与它配对，都放到输出里面
    }
    //根据位置整理输出顺序
    sort(opt.begin(), opt.end(), cmp);
    //遍历vector输出
    vector<P>::iterator iter = opt.begin();
    printf("%d\n", opt.size());
    for (; iter != opt.end(); iter++) {
        printf("%I64d ", iter->first);
    }
    printf("\n");
}

总结：
STL真好用，就是要敲各种using std::***