题意分析

1. 问题目标：
   • 将$2n$棵树的难度值分成$m$个矩形区域，每个区域的难度值为其包含树木的难度值之和。
   • 最小化所有$m$个区域中最大的难度值。
2. 限制条件：
   • 每个矩形区域必须覆盖连续的一段树（行内连续）。
   • 两行的树可以独立划分，但划分后的区域需一一对应或合并。

解题思路

1. 二分搜索框架：
   • 确定搜索范围：最小可能值为单棵树的最大难度值，最大可能值为所有树的总难度值。
   • 对于每个候选值$mid$，判断是否可以将树划分为$m$个区域，每个区域的难度值$\leq mid$。
2. 贪心验证：
   • 对每行独立进行划分，尝试在满足$\leq mid$的条件下尽可能少地划分区域。
   • 若两行划分的区域数之和$\leq m$，则$mid$可行。

实现步骤

1. 输入处理：
   • 读取两行树的难度值，并计算总难度值$sum$和单棵树的最大难度值$max\_val$。
2. 二分搜索：
   • 初始化搜索区间为$[max\_val, sum]$。
   • 对于每个$mid$，分别计算两行在$mid$限制下的最小划分区域数。
3. 验证函数：
   • 对每行从左到右累加难度值，若超过$mid$则开启新区域。
   • 返回两行区域数之和是否$\leq m$。
4. 输出结果：
   • 最终找到满足条件的最小$mid$。

代码实现

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 10005
using namespace std;
int a[3][N],f[N],nxt[3][N];
int n,m,l,r,mid,ans;
bool check(int x){
    memset(f,0,sizeof(f));
    memset(nxt,0,sizeof(nxt));
    int l1=0,l2=0,j,c;
    for (int i=1;i<=n;i++){
        while (a[1][i]-a[1][l1]>x) l1++;
        while (a[2][i]-a[2][l2]>x) l2++;
        nxt[1][i]=l1; nxt[2][i]=l2;
        if (l1==i||l2==i) return 0;
    }
    j=0;
    for (int i=1;i<=n;i++){
        f[i]=m+m; l1=l2=i; c=0;
        while (a[1][i]+a[2][i]-a[1][j]-a[2][j]>x) j++;
        f[i]=min(f[i],f[j]+1);
        while (l1+l2>0){
            c++;
            if (l1>l2) l1=nxt[1][l1];
            else l2=nxt[2][l2];
            if (l1>l2) f[i]=min(f[i],f[l1]+c);
            else f[i]=min(f[i],f[l2]+c);
        }
        if (f[i]>m) return 0;
    }
    return 1;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[1][i]);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[2][i]);
    l=0; r=1100000000;
    for (int i=1;i<=n;i++)
        a[1][i]+=a[1][i-1],a[2][i]+=a[2][i-1];
    while (l<=r){
        mid=(l+r)/2;
        if (check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    printf("%d\n",ans);
}