2018-2019 ACM-ICPC, NEERC, Southern Subregional Contest, Qualification Stage
Bacteria
Gym - 101911C
题意：像2048这个游戏，相同的两个可以合并在一起变成一个数（数值变成二倍），但是现在有一些数只有一个，所以需要添加一个和这些数相同的，让他们可以合并在一起，现在问最小添加多少个数可以把所有的数合成一个。
题解：我感觉类似于数据结构中的哈夫曼编码，最小编码，所以每次取最小的两个，如果这两个相等，就合并然后放进去，如果不相同，那就先判断2倍最小与次小的关系，如果是 2 * x1 > x2，那就没有答案了，如果不是那么 ans 。( 不过当时没想到，就极限了一下，如果ans大于某个值就默认了不可以了。）
代码语言：javascript复制#include <iostream>
#include <bits/stdc .h>
using namespace std;
typedef long long ll;
int main()
{
ll n;
while(~scanf("%lld",&n))
{
priority_queue<ll, vector<ll>, greater<ll> > q;
ll x;
for(int i = 0; i < n; i )
{
scanf("%lld", &x);
q.push(x);
}
ll cnt = 0;
ll x1, x2;
ll f = 0;
if(n == 1) {printf("0n");continue;}
while(!q.empty())
{
x1 = q.top();
q.pop();
if(!q.empty())
{
x2 = q.top();
if(x1 == x2)
{
x1 = x1 x2;
q.pop();
q.push(x1);
}
else {
x1 = 2 * x1;
q.push(x1);
cnt ;
}
}
else {
break;
}
if(cnt > 3e5) {f = 1;break;}
}
if(f==0)printf("%lldn",cnt);
else printf("-1n");
}
return 0;
}
