天元编程邀请赛两人三足

链接：登录—专业IT笔试面试备考平台_牛客网

大马猴和机智羊打算参加运动会的两人三足项目（两个人并排跑，中间两条腿绑在一起），为此，机智羊甚至学会了站立走路ヾ(≧▽≦*)o，为了备战比赛，他们预计要做一些默契度训练。

大马猴正常走路每走一步的距离为 x，机智羊每走一步的距离为 y。但在两人三足项目中，他们每走一步的距离必须一样。

如果大马猴花了 a1​ 天去调整，他可以将步长改为 x−1∼x+1 中任何一个数；如果他花了 a1+a2 天去调整，那么他可以将步长改为 x−2∼x+2 中任何一个数。即，如果大马猴花费 a1​+a2​+a3​+…+an​ 天，则他可以把走一步的距离改为 x−n∼x+n中任何一个数；同理，机智羊花费 b1+b2+b3+...+bm天，则他可以把走一步的距离改为 y−m到y+m中任何一个数。注意，a,b 可能为负数，即如果只想改距离 3，可能 a1+a2+a3+a4+a5​ 会比 a1+a2+a3 更优。

大马猴最多只能改 n步，机智羊最多只能改 m 步，因为他俩的腿长是有限的。注意不能多轮调整，调整到的步长必须是正整数。

请问至少需要多少天，才能让他俩走一步的距离一样。数据保证一定有解，且最优解一定大于 0 。

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

输入描述:

第一行，包含四个正整数 x，y，n，m，具体含义如题面所示。

第二行，包含 nnn 个整数 ai​。

第三行，包含 mmm 个整数 bi​。

输出描述:

一行一个整数，表示至少需要多少天。

示例1

输入

复制6 3 2 2 2 2 1 -1

6 3 2 2
2 2
1 -1

输出

复制2

2

说明

最优解为两个人调整步距为 5 ：

大马猴需要改变 1 格距离，需要 2 天；机智羊需要改变 2 格距离，需要 1+(−1)=0天，所以至少需要 2天。

当时写的时候用啦两重循环遍历超时啦，看啦别人的题解，感觉处理的秒不可言，优化为转化为一重循环

处理：

维护一个数组，a[i]表示从i到最后对与原前缀和数组中最小的数。这样做，我的理解是将一些可行解合并，就不用遍历啦。如果大马猴调整i可行，那么调整i+k一定可行，所以记录a[i]为i~n的最小值

代码：

#include 
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main()
{
    int x,y,n,m;
    int ans=2e9;
    cin>>x>>y>>n>>m;
    for(int i=1;i<=n;i++) {scanf("%d",&a[i]);a[i]+=a[i-1];}
    for(int i=1;i<=m;i++) {scanf("%d",&b[i]);b[i]+=b[i-1];}   //前缀和数组
    for(int i=n-1;i>0;i--) a[i]=min(a[i],a[i+1]);  //a[i]表示从i位置到最后的前缀和最小的哪个
    for(int i=m-1;i>0;i--) b[i]=min(b[i],b[i+1]);  //b[i]同a[i];
        int c=abs(x-y);
    for(int i=0;i<=n;i++)  //这里n不可以改为c,因为有c>n的情况
        if(c-i<=m) ans=min(ans,max(a[i],b[c-i]));    
    cout<