题解：P14597 [COCI 2025/2026 #2] 递增 / Rastući

I_am_kunzi · 2025-11-26 19:20:48 · 题解

P14597 题解

前言：受题解区启发，我自己造了一个加强版题目。这里是加强版题目。当然如果这道题有不完善的地方欢迎补充。

题目思路

我们发现合并一定是相邻两数合并，所以最终的答案序列中每一个数都在原序列中对应一个连续的段。而且如果想要最终答案序列的长度尽可能大，每一个段的长度就要尽可能短，也就是最终答案序列中每个数都要尽可能小。

从上一段可知，如果固定当前这个数在原序列中对应区间的右端点，那么左端点就要尽可能大。所以我们只需要记录每一个点 i 作为右端点时最大的左端点 f_i，转移时根据 i 的信息推出下一段的右端点 j 并更新 f_j 的值。

另外 f_{i + 1} 的值可以从 f_i 转移，从含义上可以知道此时相当于增大当前答案序列末尾的数，整个答案序列仍然单调不减。

题目代码

此份代码中数组范围与加强版一致，所以这也可以是加强版题目的题解。

#include<bits/stdc++.h>
using namespace std;
int f[500005]; // 记录每一段 f[i] ~ i
long long a[500005] , qzh[500005];
int n;
int find(int i) // 当前这一段是 f[i] ~ i，找下一段 i + 1 ~ x
{
    long long sum = qzh[i] - qzh[f[i] - 1]; // 当前段的答案
    return lower_bound(qzh + 1 , qzh + n + 1 , sum + qzh[i]) - qzh; // 寻找最小的下一段结尾
}
signed main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i];
        qzh[i] = qzh[i - 1] + a[i];
        f[i] = 1;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        f[i] = max(f[i] , f[i - 1]); // 这一段直接加一个数仍然单调不降
        int pos = find(i);
        long long sum2 = qzh[pos] - qzh[i];
        if(sum2 < qzh[i] - qzh[f[i] - 1]) // 注意判断当前的答案是否可行
        {
            continue;
        }
        f[pos] = max(f[pos] , i + 1); // 更新计算出的下一段右端点
    }
    long long maxx = 0 , pos = 0;
    vector < long long > ans;
    for(int i = n ; i >= 1 ; i--)
    {
        maxx++;
        ans.push_back(qzh[i] - qzh[f[i] - 1]);
        i = f[i];
    }
    cout << maxx << endl;
    sort(ans.begin() , ans.end()); // 直接排序就可以得到单调不减顺序
    for(long long i : ans)
    {
        cout << i << ' ';
    }
}