题目大意

• 给定正整数序列 $a_1,\ a_2,\ \cdots,\ a_n$。

• 要求每次从序列中找出最小的 $x$，且出现次数至少为 $2$，再找到最小的 $i<j$，使得 $a_i=a_j=x$，接着将 $a_i$ 从序列中删除，最后将 $a_j$ 修改为 $2x$。

• 如此操作直到这个序列无法继续操作，输出这个序列。

• $2\leq n\leq 1.5\times 10^5$，$1\leq a_i\leq 10^9$

解题思路

首先将整个序列中每个数的下标（也就是 $1\sim n$）放入优先队列中，而该优先队列按照下标对应的值从小到大排序。

每次从优先队列中取出两个下标 $i,\ j$，则 $a_i,\ a_j$ 必为此时序列中最小的两个数，下面分类讨论：

• 若 $a_i=a_j$，则直接进行合并，将原序列的 $a_j$ 值替换为 $2a_j$；

• 若 $a_i\not=a_j$，由于 $a_i,\ a_j$ 是此时序列中最小的两个数，故序列中仅存在一个 $a_i$，每次操作数只会变大，那么此数无法合并。只需把它弹出队列，把下标加入答案数组即可。

最后队列中只剩下一个数，直接加入答案数组即可。

输出时，只需按照下标从小到大排序，再输出对应的数值即可。

时间复杂度 $\Theta(n\log n)$。

AC 代码

#include<bits/stdc++.h>
using namespace std;

int n; long long a[150001];

struct Cmp{
    bool operator()(int x,int y){
        if(a[x]!=a[y])return a[x]>a[y];
        else return x>y;
    }
};
priority_queue<int,vector<int>,Cmp> Q;
vector<int> answer;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
        scanf("%lld",a+i),Q.push(i);
	while(Q.size()>=2){
		int x=Q.top(); Q.pop();
        int y=Q.top(); Q.pop();
        if(a[x]==a[y])a[y]<<=1,Q.push(y); // 数值翻倍再放回优先队列
        else Q.push(y),answer.push_back(x); // 直接加入答案序列
	}
    if(!Q.empty())answer.push_back(Q.top());
	printf("%d\n",int(answer.size()));
    sort(answer.begin(),answer.end()); //对下标排序
    for(int i : answer)
        printf("%lld ",a[i]);
    printf("\n");
	return 0;
}