Atcoder Beginner Contest 323D

Atcoder Beginner Contest 323D

D - Merge Slimes

问题陈述

初始时有$N$种大小的史莱姆。

具体地，对于每个$1 <= i <= N$，有$C_i$个大小为$S_i$的史莱姆。

Takahashi 可以任意多次进行史莱姆合成（可能是零次），并且顺序可以任意。

史莱姆合成的过程如下：

选择两个大小相同的史莱姆，设其大小为$X$，然后生成一个大小为$2X$的新史莱姆。两个原始的史莱姆会消失。

Takahashi 希望最小化史莱姆的数量。通过最优的合成顺序，他最终能得到的最小史莱姆数量是多少？

算法

二进制枚举 贪心

代码

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n"
#define EPS 1e-8
#define IOS ios::sync_with_stdio(0),cin.tie(0)
#define all(v) v.begin(),v.end()
using namespace std;
using i64 = long long;
using ull = unsigned long long;
using pi = pair<int,int>;
using pl = pair<long long,long long>;
static constexpr int ALPHABET_SIZE = 26;
static constexpr int N = 1000000 + 5;
static constexpr int MOD = 998244353;

void merge(auto& m, i64 num, i64 cnt) {
    i64 pow2 = 2;
    for (int i = 1; i <= 30; i++) {
        if (cnt >> i & 1) {
            m[num * pow2]++;
            m[num] -= pow2;
        }
        pow2 *= 2;
    }
}

void solve() {
    //可以把两个相同的数x， 变为一个数2x
    //问最少能把给定的n个数减为多少个数
    //直接全和了, 排序
    int n;
    cin >> n;
    map<i64, i64> m;
    for (int i = 0; i < n; i++) {
        i64 num, cnt;
        cin >> num >> cnt;
        m[num] += cnt;
    }
    i64 res = 0;
    for (auto& [k, v]: m) {
        merge(m, k, v);
        res += v;
    }
    cout << res;
}
int main()
{
    IOS;
    int t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
    return 0;     
}