題目:
http://codeforces.com/problemset/problem/962/D
大意:
給你一個(gè)數(shù)列扮碧,如果一個(gè)數(shù)字出現(xiàn)兩次杏糙,則刪除左邊的那個(gè),右邊的數(shù)值*2赖淤。求最終得到的數(shù)列谅河。
思路:
用一個(gè)優(yōu)先隊(duì)列,以數(shù)值大小為主排序绷耍,模擬上述過(guò)程褂始。將剩余元素以數(shù)組下標(biāo)排序,輸出崎苗。
數(shù)值翻倍后有可能超出int范圍赘阀,要使用long long脑奠。
代碼:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<ll,ll>p;
priority_queue<p,vector<p>,greater<p> >que;
priority_queue<p,vector<p>,greater<p> >a;
int main(){
ll n;
while(cin>>n){
ll cnt=0;
for(ll i=0;i<n;i++){
ll t;
cin>>t;
que.push(p{t,i});}
while(!que.empty()){
p x=que.top();
que.pop();
if(!que.empty()&&x.first==que.top().first){
p e=que.top();
que.pop();
que.push(p{e.first*2,e.second});
}
else{
a.push(p{x.second,x.first});
}
}
cout<<a.size()<<endl;
cout<<a.top().second;
a.pop();
while(!a.empty()){
cout<<" "<<a.top().second;
a.pop();
}
}
}