递推+模拟，CF 748E - Santa Claus and Tangerines

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

748E - Santa Claus and Tangerines

---

二、解题报告

1、思路分析

如果 x 是答案，那么 能够分成的 size > x 的 集合 的数目 >= k

我们记 cnt[x] 为 能够划分 size = x 的集合的数目

cnt[x] 如何快速得到？

cnt[x] = cnt[2x + 1] + cnt[2x]

我们维护cnt[]，cnt 初始为 a[] 中的元素计数数组

然后倒序递推，维护一个cur，代表当前 >= i 的 集合的数目

首先 cur += cnt[i]，即初始的 i 的数目

然后递推

cnt[i] += cnt[2i + 1]

cnt[i] += cnt[2i]

cnt[i + 1] += cnt[2i + 1]

cur += cnt[2i + 1]

cur += cnt[2i]

如果 i >= k，我们输出 i 即可

上述递推的过程其实是 不断模拟的过程，随着我们答案的限制越来越小，原来不能划分的集合逐渐能够划分，贡献随之累加到 cur

2、复杂度

时间复杂度： O(N + M)空间复杂度：O(N + M)

3、代码详解

 ​

#include <bits/stdc++.h>

// #define DEBUG

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

void solve() {
    int n, k;
    std::cin >> n >> k;

    std::vector<int> a(n);
    int M = 0;
    for (int i = 0; i < n; ++ i) {
        std::cin >> a[i];
        M = std::max(M, a[i]);
    }

    std::vector<i64> cnt(M + 1);
    for (int x : a)
        ++ cnt[x];

    i64 cur = 0;

    for (int i = M; i; -- i) {
        cur += cnt[i];

        if (i * 2 + 1 <= M) {
            cur += cnt[2 * i + 1];
            cnt[i] += cnt[i * 2 + 1];
            cnt[i + 1] += cnt[i * 2 + 1];
        }

        if (i * 2 <= M) {
            cur += cnt[i * 2];
            cnt[i] += cnt[i * 2] * 2;
        }

        if (cur >= k) {
            std::cout << i << '\n';
            return;
        }
    }

    std::cout << "-1\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

#ifdef DEBUG
    int cur = clock();
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int t = 1;
    // std::cin >> t;

    while (t--) {
        solve();
    }
#ifdef DEBUG
    std::cerr << "run-time: " << clock() - cur << '\n';
#endif
    return 0;
}

原文地址：https://blog.csdn.net/EQUINOX1/article/details/142742731

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！