解题思路: 首先判断给定的数n是否是2的正整数次幂,如果是,则输出n的二进制表示即可,因为任何一个2的正整数次幂都可以表示为2的幂次方的和。

如果n不是2的正整数次幂,那么我们需要找到拆分后的数中是否存在相同的数,如果存在,则输出-1,表示不存在优秀的拆分。

具体的做法是,对于每个数i从2开始,判断n是否可以被i的幂次方整除,如果可以,则将i的幂次方加入到拆分方案中,同时将n除以i的幂次方得到新的n,继续判断新的n是否可以被i的幂次方整除,直到n无法被i的幂次方整除为止。

如果拆分方案中存在相同的数,则输出-1,否则将拆分方案按照从大到小的顺序输出即可。

C++代码实现如下:

#include <iostream>
#include <vector>
using namespace std;

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

vector<int> excellentPartition(int n) {
    vector<int> partition;
    if (isPowerOfTwo(n)) {
        for (int i = 0; i < 32; i++) {
            if ((n >> i) & 1) {
                partition.push_back(1 << i);
            }
        }
    } else {
        for (int i = 2; i <= n; i++) {
            while (n % i == 0) {
                partition.push_back(i);
                n /= i;
            }
        }
        if (partition.size() > 1) {
            for (int i = 1; i < partition.size(); i++) {
                if (partition[i] == partition[i-1]) {
                    partition.clear();
                    partition.push_back(-1);
                    break;
                }
            }
        }
    }
    return partition;
}

int main() {
    int n;
    cin >> n;
    
    vector<int> partition = excellentPartition(n);
    for (int i = partition.size() - 1; i >= 0; i--) {
        cout << partition[i] << " ";
    }
    
    return 0;
}
``

原文地址: http://www.cveoy.top/t/topic/iWwS 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录