题目:
http://codeforces.com/problemset/problem/962/D
大意:
给你一个数列,如果一个数字出现两次,则删除左边的那个,右边的数值*2。求最终得到的数列。
思路:
用一个优先队列,以数值大小为主排序,模拟上述过程。将剩余元素以数组下标排序,输出。
数值翻倍后有可能超出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();
}
}
}