https://codeforces.com/contest/962/problem/D
题目大意
给出 $n \ (\le 150,000)$ 长的数组 $a$，其中 $1 \le a_i \le 10^9$。执行如下操作，直到不能进行为止：
找到出现两次以上的所有数中最小的数，然后在这个数当前的所有下标里选择最小的两个 $i$ 和 $j$。将 $a[i]$ 删去 $a[j] \gets a[i] + a[j]$。
问最终状态的数组是什么。
简要题解
显然每次操作我们都会合并一对数（删去一对数）也就是说最多也就是进行 $n - 1$ 次操作。而数字大也就是所有数字的和。因此用 long long 没有溢出的问题。
剩下的就是每次找到一组相同的数。这个可以有很多维护方法，但是最简单的就是直接从小向大看依次能不能合并，显然合并了的数会更大，所以当还没处理的最小的 $x$，只有一个时，意味着所有比它小的数字目前都是单个，它也合并不了就会剩到最后的结果，其他时候需要选取两个相同数的最小下标。因此优先队列就是按照 $(val, id)$ 二元组的升序弹出就可以。
复杂度
$T$：$O(n \log n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
struct Node {
LL v;
int p;
bool operator<(const Node& B) const {
return v != B.v ? v > B.v : p > B.p;
}
};
void solve() {
int n; cin >> n;
vector<LL> a(n);
for (LL& i : a) cin >> i;
priority_queue<Node> qu;
for (int i = 0; i < n; i++) {
qu.push({a[i], i});
}
vector<int> valid(n, 1);
while (!qu.empty()) {
auto [va, pa] = qu.top(); qu.pop();
if (qu.empty() || qu.top().v != va) {
continue;
}
auto [vb, pb] = qu.top(); qu.pop();
// cerr << va << ' ' << pa << ' ' << pb << endl;
valid[pa] = 0;
a[pb] += a[pa];
qu.push({a[pb], pb});
}
int m = 0;
for (int i = 0; i < n; i++) {
if (valid[i]) m++;
}
cout << m << '\n';
for (int i = 0; i < n; i++) {
if (valid[i]) {
cout << a[i] << (--m ? ' ' : '\n');
}
}
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] D. Edge Deletion - Educational Codeforces Round 54 (Rated for Div. 2)