题目链接：http://codeforces.com/contest/962/problem/D
题意：输入n，接下来输入n个数ai。每次从左往右，如果某个数字出现次数>=2，记出现次数>=2中最小的数为x，把前面那个x消除，后面的x变成2x。然后一直执行这个操作，直到无法执行，输出最后保留下来的数字，顺序和操作中的不变。
分析：一看到每次消掉最小的x，然后把下标大的x变成2x，就想要利用优先队列，id小的在队头，对于每一个数字的优先队列p[x]存储所有值为x数的id，然后优先队列q[x] pop两次，代表合并两个x，接着在2x那个队列中q[2x] push刚才两个x中的大id，直到q[x].size()<2。然后判断q[2x]的size()，继续这个操作。直到最后这些数字q[x].size()都小于2。由于数字x较大，我们需要对离散化，用map存储每一个数字离散化之后的序号，用数组b存map后的序号对应的x，即mp[x]=s，b[s]=x，x对应的优先队列为q[mp[x]]。当把数字消除更新之后，每个队列中最多只有一个id，然后每个队列q[i]对应的数字就是b[i]。按照id从小到大，输出size()=1的数字就可以了，这个比较简单。
AC代码：
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 priority_queue<int,vector<int>,greater<int> >q[1000005]; 6 map<long long ,int>mp; 7 long long a[1000005]; 8 long long b[1000005]; 9 int id[1000005],dd[1000005]; 10 bool cmp(int x,int y){ 11 return id[x]<id[y]; 12 } 13 int main(){ 14 ios_base::sync_with_stdio(0); 15 cin.tie(0); 16 int n; 17 memset(id,0x3f3f3f3f,sizeof(id)); 18 cin>>n; 19 int ans=0; 20 for(int i=1;i<=n;i++){ 21 cin>>a[i]; 22 if(mp[a[i]]==0){ 23 ans++; 24 mp[a[i]]=ans; 25 b[ans]=a[i]; 26 } 27 q[mp[a[i]]].push(i); 28 } 29 sort(a+1,a+1+n); 30 for(int i=1;i<=n;i++){ 31 long long s=a[i]; 32 for(int j=1;j<=64;j++){ 33 if(q[mp[s]].size()<2) break; 34 long long s2=s*2; 35 if(mp[s2]==0){ 36 ans++; 37 mp[s2]=ans; 38 b[ans]=s2; 39 } 40 int d1=mp[s],d2=mp[s2]; 41 while(q[d1].size()>=2){ 42 q[d1].pop(); 43 int d=q[d1].top(); 44 q[d1].pop(); 45 q[d2].push(d); 46 } 47 s=s*2; 48 } 49 } 50 int num=0; 51 for(int i=1;i<=ans;i++){ 52 dd[i]=i; 53 if(q[i].size()==1){ 54 num++; 55 id[i]=q[i].top(); 56 } 57 } 58 sort(dd+1,dd+1+ans,cmp); 59 cout<<num<<endl; 60 for(int i=1;i<=ans;i++){ 61 if(id[dd[i]]==0x3f3f3f3f){ 62 break; 63 } 64 cout<<b[dd[i]]<<" "; 65 } 66 cout<<endl; 67 return 0; 68 }