社区讨论

我暴力能过?

P1631序列合并参与者 3已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@m1qhnczu
此快照首次捕获于
2024/10/01 21:42
去年
此快照最后确认于
2025/11/04 18:21
4 个月前
查看原帖
我用了比较暴力的解法,为什么竟能通过这题呢?

CPP
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        cin >> b[i];
    vector<int> mins;
    for (int i = 0; i < n; ++i)
    {
        bool any = false;
        for (int j = 0; j <= i; ++j)
        {
            int sum = 0;
            sum = a[j] + b[i - j];
            if (mins.size() < n || sum <= mins[n - 1])
            {
                any = true;
                mins.insert(upper_bound(mins.begin(), mins.end(), sum), sum);
                if (mins.size() > n)
                    mins.pop_back();
            }
        }
        if (!any)
            break;
    }
    for (int i = 0; i < n; ++i)
    {
        if (i > 0)
            cout << ' ';
        cout << mins[i];
    }
    cout << '\n';
    return 0;
}

回复

9 条回复,欢迎继续交流。

正在加载回复...