题解+答题思路

这道题主要考察对数字拆分和二进制表示的理解，解题的关键在于利用2的幂次特性和贪心策略

核心思路

1. 问题分析

   • 优秀的拆分要求将正整数n分解为不同的2的正整数次幂之和（即2¹, 2², 2³...，不包括2⁰=1）。
   • 例如：10 = 8 + 2 = 2³ + 2¹ 是优秀的拆分，而7 = 4 + 2 + 1 不是（因为1不是2的正整数次幂）。

2. 关键判断

   • 奇数直接排除：由于2的正整数次幂都是偶数，任何奇数都无法拆分为偶数之和，因此直接输出-1。
   • 偶数的处理：对于偶数n，需要进一步判断是否能拆分为不同的2的正整数次幂之和。

3. 贪心策略

   • 从最大的2的幂次开始尝试：每次选择不超过当前剩余值的最大2的幂次，确保拆分出的数字互不相同且尽可能大。
   • 二进制思想：每个偶数都可以用二进制表示，其二进制位上为1的位置对应2的幂次。例如，6的二进制是110，对应2² + 2¹ = 4 + 2。

解题步骤

1. 输入处理

   • 读取整数n，判断奇偶性。若为奇数，直接输出-1并结束。

2. 拆分过程

   • 初始化剩余值current = n和计数器cnt。
   • 从最大可能的2的幂次（如2³⁰，覆盖题目范围1e7）开始逆序遍历：
     • 对于每个幂次power = 2^i，若power ≤ current，则将其加入拆分结果，并更新current -= power。
     • 若current减为0，说明拆分完成，提前退出。

3. 输出结果

   • 若最终current为0，按从大到小输出拆分结果；否则输出-1。

代码实现关键点

• 幂次计算：使用位移运算1 << i代替pow(2, i)，避免浮点数误差。
• 数组存储：用数组记录拆分出的2的幂次，确保顺序正确。
• 输出格式：注意最后一个数字后不能有多余空格。

复杂度分析

• 时间复杂度：O(log n)，主要来自遍历2的幂次。
• 空间复杂度：O(log n)，最坏情况下需要存储所有2的幂次。

通过这种方法，可以高效且正确地判断并输出优秀的拆分方案。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e3 + 5;
int arr[N];

int main()
{
    int n;
    cin >> n;
    if (n % 2 != 0) // 2的正整数次幂都为偶数，奇数不存在优秀拆分
        cout << -1 << endl;
    else
    {
        int cnt = 0;
        int current = n;

        for (int i = 30; i >= 1; i--) 
        {
            int power = 1 << i;
            if (power <= current)
            {
                arr[cnt++] = power;
                current -= power;
            }
            if (current == 0) 
                break;
        }

        if (current == 0)
        {
            for (int i = 0; i < cnt; i++) 
            {
                cout << arr[i];
                if (i < cnt - 1) 
                    cout << ' ';
            }
            cout << endl;
        }
        else 
            cout << -1 << endl;
    }

    return 0;
}