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 𝑥 that occurs in the array 2 or more times. Take the first two occurrences of 𝑥 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⋅𝑥).
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 𝑛 (2≤𝑛≤150000) — the number of elements in the array.
The second line contains a sequence from 𝑛 elements 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤109) — the elements of the array.
Output In the first line print an integer 𝑘 — the number of elements in the array after all the performed operations. In the second line print 𝑘 integers — the elements of the array after all the performed operations.
Examples inputCopy 7 3 4 1 2 2 1 1 outputCopy 4 3 8 2 1 inputCopy 5 1 1 3 1 1 outputCopy 2 3 4 inputCopy 5 10 40 20 50 30 outputCopy 5 10 40 20 50 30 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.
题意: 选出最小的那个出现了至少两次的数,把这个数最左边那个删掉,次左边那个乘以2。 求最终的序列
思路: 优先队列+map模拟(貌似写的常数巨大
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include <set> #include <map> #include <queue> using namespace std; typedef long long ll; const int maxn = 3e5 + 7; map<ll,int>mp; ll a[maxn]; map<ll,int>num,vis; priority_queue<int>q[maxn]; struct Node { ll x; bool operator < (const Node& rhs) const{ if(x == rhs.x) return num[x] < num[rhs.x]; return x > rhs.x; } }; priority_queue<Node>Q; int main() { int n;scanf("%d",&n); int cnt = 0; for(int i = 1;i <= n;i++) { scanf("%lld",&a[i]); num[a[i]]++; if(!mp[a[i]]) mp[a[i]] = ++cnt; q[mp[a[i]]].push(-i); } for(int i = 1;i <= n;i++) { if(!vis[mp[a[i]]]) { Node now; now.x = a[i]; if(num[a[i]] >= 2) Q.push(now); vis[mp[a[i]]] = 1; } } while(!Q.empty()) { Node now = Q.top();Q.pop(); ll x = now.x; num[x] -= 2; int pos1 = -q[mp[x]].top();q[mp[x]].pop(); int pos2 = -q[mp[x]].top();q[mp[x]].pop(); if(!mp[x * 2]) mp[x * 2] = ++cnt; q[mp[x * 2]].push(-pos2); num[x * 2]++; a[pos1] = 0; a[pos2] = x * 2; if(num[x] >= 2) Q.push(now); if(num[x * 2] == 2) { Node now; now.x = x * 2; Q.push(now); } } cnt = 0; for(int i = 1;i <= n;i++) { if(a[i]) cnt++; } printf("%d\n",cnt); for(int i = 1;i <= n;i++) { if(a[i]) printf("%lld ",a[i]); } return 0; }