我暴力能过?
  • 板块P1631 序列合并
  • 楼主Zaoly
  • 当前回复8
  • 已保存回复8
  • 发布时间2024/10/1 21:42
  • 上次更新2024/10/2 09:25:09
查看原帖
我暴力能过?
349869
Zaoly楼主2024/10/1 21:42

我用了比较暴力的解法,为什么竟能通过这题呢?


#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;
}
2024/10/1 21:42
加载中...