2020 优秀的拆分 · 方案一贪心从大到小减

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 1/5 · 共 932 字

打 2 的幂表，从大到小各取一次

2020
位运算

正文

// CSP-J 2020 复赛 T1 · 优秀的拆分
// 原题：https://oj.yecheng.tv/p/CSPJ2020A
// 题意：把 n 拆成若干个「互不相同的 2 的正整数次幂」之和，从大到小输出；
// 做不到就输出 -1。（1 = 2^0 不算正整数次幂，所以奇数一定做不到。）
//
// 方案一 · 贪心从大到小减
// 先打一张 2 的幂表：2, 4, 8, ... 直到超过 n。
// 从最大的幂开始试：只要当前的幂不超过剩下的数，就把它取走一次。
// 因为每种幂最多只能用一次，所以这里是 if 而不是 while。
// 复杂度：O(log n)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("power.in", "r", stdin);
    freopen("power.out", "w", stdout);

    int n;
    cin >> n;

    // 奇数一定无解：2 的正整数次幂全是偶数，偶数加不出奇数
    if (n % 2 == 1) {
        cout << -1 << "\n";
        return 0;
    }

    int pw[32];
    pw[0] = 1;
    for (int i = 1; i <= 30; i++) pw[i] = pw[i - 1] * 2;

    bool first = true;
    for (int i = 30; i >= 1; i--) {        // 从大到小，正好满足输出顺序
        if (n >= pw[i]) {
            n -= pw[i];
            if (!first) cout << " ";
            cout << pw[i];
            first = false;
        }
    }
    cout << "\n";
    return 0;
}

2020 优秀的拆分 · 方案一 贪心从大到小减

正文

CSP-J 标程 · 复赛真题的其它内容

2020 优秀的拆分 · 方案一贪心从大到小减