T101040.连接二进制片段得到的最大值

https://leetcode.cn/problems/maximum-value-of-concatenated-binary-segments/

【黄宇曦 地球与空间科学学院】一个比较显著的贪心是 a+b>b+a，但是极限情况下可能超时，等价翻译为 nums1 和 nums2 的版本即可。

时间复杂度 $O(n\log n+\sum n_i)$。

const int MOD = 1e9 + 7;

class Solution {

public:
    int maxValue(vector<int>& nums1, vector<int>& nums0) {
        vector<string> ret;
        int n = nums1.size();
        // for (int i = 0; i < n; i++) {
        //     ret.push_back(string(nums1[i], '1') + string(nums0[i], '0'));
        // }
        // sort(ret.begin(), ret.end(),
        //      [](auto& a, auto& b) { return a + b > b + a; });
        vector<int> tmp(n);
        iota(tmp.begin(), tmp.end(), 0);
        sort(tmp.begin(), tmp.end(), [&](int a, int b) {
            if (nums0[a] == 0 || nums0[b] == 0) {
                return nums0[a] < nums0[b];
            }
            return nums1[a] != nums1[b] ? nums1[a] > nums1[b]
                                        : nums0[a] < nums0[b];
        });
        for (int i = 0; i < n; i++) {
            ret.push_back(string(nums1[tmp[i]], '1') +
                          string(nums0[tmp[i]], '0'));
        }
        string s;
        s.reserve(200005);
        for (auto& str : ret)
            s += str;
        reverse(s.begin(), s.end());
        int ans = 0, qpow = 1;
        for (int i = 0; i < s.size(); i++, qpow = (1ll * qpow * 2) % MOD) {
            if (s[i] == '1') {
                ans = (1ll * ans + qpow) % MOD;
            }
        }
        return ans;
    }
};