洛谷 CF962D Merge Equals 省选 优先队列 c++

查看题目信息

给定一个正整数序列，这里面至少有2个数相同。

我们执行如下操作：找到最小的数值x（x重复出现了2次或2次以上），删除第1次出现的x，将第2次出现的x改为2*x（数值在原来基础上乘以2），直到序列中没有哪个数值重复出现2次或2次以上。

比如：给定序列[3,4,1,2,2,1,1].将按如下方式进行变化：[3,4,1,2,2,1,1]->[3,4,2,2,2,1]->[3,4,4,2,1]->[3,8,2,1]

第1行包含一个正整数n(2<=n<=150000)，表示序列中元素的个数。

第2行包含n个正整数a1,a2,...,an(1<=ai<=10^9)

第一行打印一个整数k，表示序列最终形态所包含元素的个数。

第2行打印k个整数，表示序列的最终形态

此题可以用优先队列和结构体，存储每个数的位置（pos)和值（x)

#优先队列基本操作：

定义优先级：

struct cmp

{

    bool operator （）（noid x,noid y)

    {

             return 排序规则

     }

}

定义优先对列 priority_queue,cmp> q;

入队 q.push()                 出队 q.pop()             队首 q.front()

#正解

#include
using namespace std;
struct noid
{
	long long x,id;
};
struct cmp
{
	bool operator ()(noid x,noid y)
	{
		if(x.x==y.x)
		{
			return x.id>y.id;
		}
		else return x.x>y.x;
	}
};
priority_queue,cmp> q;
long long a[1000010];
int main()
{
    int n,i,j,k;
    cin>>n;
    for(i=1;i<=n;i++)
    {
    	cin>>a[i];
    	q.push(noid{a[i],i});
	}
	while(q.size()>1)
	{
		noid t1=q.top();
		q.pop();
		noid t2=q.top();
		q.pop();
		if(t1.x==t2.x)
		{
			a[t1.id]=-1;
			t2.x*=2;
			a[t2.id]=t2.x;
			q.push(t2);
		}
		else
		{
			q.push(t2);
		}
	}
	int ans=0;
	for(i=1;i<=n;i++)
	{
		if(a[i]!=-1) ans++;
	}
	cout<