满足条件的最大组合

Tag: 笔试算法题 Posted on 2022-03-19 13:37:01 Edited on 2022-03-22 21:44:09 Views: 168

概述

有一个数组,要你找出最大的组合,使得该组合中元素的和能被 k1 整除但是不能被 k2 整除, 问最大值是多少且能达到最大值的组合个数。

回溯法

回溯法暴力遍历所有可能。

根据 JW 反馈超时。

分治

给定一个序列,将其分为两个子序列,每个子序列分别计算自己所有可能的和,并统计出现次数。

虽然也很暴力吧,但是,对于出现的和相同的组合方法,我们只需要和别人组合一次。

写的时候别忘了,当前区间也可以不选择,所以要有 res[0] = 1;

#include <bits/stdc++.h>

using namespace std;

unordered_map<int, int> helper(vector<int> &nums, int l, int r) {
    unordered_map<int, int> res;
    if (l == r) {
        res[0] = 1;
        res[nums[l]] = 1;
        return res;
    }
    int m = (l + r) / 2;
    auto m1 = helper(nums, l, m);
    auto m2 = helper(nums, m + 1, r);
    for (auto &iter1: m1) {
        for (auto &iter2: m2) {
            res[iter1.first + iter2.first] += iter1.second * iter2.second;
        }
    }
//    cout << "l " << l << " r " << r << " -> ";
//    for (auto & iter : res) {
//        cout << iter.first << " ";
//    }
//    cout << endl;

    return res;
}

int main() {
    int n, k1, k2;
    cin >> n >> k1 >> k2;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    auto ans = helper(nums, 0, n - 1);
    int res = 0;
    int count = 0;
    for (auto &iter: ans) {
        if (iter.first % k1 == 0 && iter.first % k2 != 0) {
            if (iter.first > res) {
                res = iter.first;
                count = iter.second;
            }
            res = max(res, iter.first);
        }
    }
    cout << res << " " << count;
}

测试:

输入:
10 4 6
0 1 2 3 4 5 6 7 8 9

输出:44 8

未经允许,禁止转载,本文源站链接:https://iamazing.cn/