4.12日字节跳动笔试1,3,4题解，求一波第2题题解

#include <iostream>

using namespace std;

const int maxn = 1000005;
int a[maxn],b[maxn],c[maxn];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i = 0; i < n; i++) scanf("%d",&a[i]);
        for(int i = 0; i < n; i++) scanf("%d",&b[i]);
        for(int i = 0; i < n; i++) c[i] = b[i] - a[i];
        int l = 0;
        while(l < n && c[l] == 0) l++;
        if(l == n)
        {
            printf("YES\n");
        }
        else
        {
            int r = l + 1;
            while(r < n && c[r] != 0) r++;
            bool flag = true;
            for(int i = l; i < r - 1; i++)
            {
                if(c[i] != c[i + 1] || c[i] < 0)
                {
                    flag = false;
                    break;
                }
            }
            if(!flag)
            {
                printf("NO\n");
            }
            else
            {
                bool flag2 = true;
                for(int i = r; i < n; i++)
                {
                    if(c[i] != 0)
                    {
                        flag = false;
                        break;
                    }
                }
                if(!flag)
                {
                    printf("NO\n");
                }
                else
                {
                    printf("YES\n");
                }
            }
        }
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1000005;
typedef long long LL;
int a[maxn],b[maxn];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);
    for(int i = 0; i < m; i++) scanf("%d",&b[i]);
    sort(a, a + n);
    sort(b, b + m);
    LL ans = 0;
    for(int i = 0; i < m; i++)
    {
        int *p = lower_bound(a,a + n,b[i]);
        if(!p) ans += (b[i] - a[n - 1]);
        else
        {
            if(*p == b[i]) ans += 0;
            else
            {
                if(p == a) ans += b[i];
                else ans += (b[i] - *(p - 1));
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

#include <iostream>

using namespace std;
const int maxn = 100005;
int a[maxn];
int dpl[maxn],dpr[maxn];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i = 0; i < n; i++) scanf("%d",&a[i]);
        dpl[0] = 0;
        for(int i = 1; i < n; i++)
        {
            if(a[i] >= a[i - 1])
            {
                int j = dpl[i - 1];
                while(j - 1 >= 0 && a[i] >= a[j - 1])
                {
                    j = dpl[j - 1];
                }
                dpl[i] = j;
            }
            else
            {
                dpl[i] = i;
            }
        }
        dpr[n - 1] = n - 1;
        for(int i = n - 2; i >= 0; i--)
        {
            if(a[i] >= a[i + 1])
            {
                int j = dpr[i + 1];
                while(j + 1 < n && a[i] >= a[j + 1])
                {
                    j = dpr[j + 1];
                }
                dpr[i] = j;
            }
            else
            {
                dpr[i] = i;
            }
        }
        for(int i = 0; i < n; i++)
        {
            if(i == n - 1) printf("%d\n",dpr[i] - dpl[i]);
            else printf("%d ",dpr[i] - dpl[i]);
        }
    }
    return 0;
}