题目描述

不患寡而患不均,不患贫而患不安。

​ 蛤蟆先生和他的三个兄弟得到了一条长度为 $L$ 的巧克力,巧克力上有 $N-1$个纹路,每个纹路所在位置 $ x_i$ 都可以折断。现在他们想把巧克力尽可能折成平均的 $4$ 段,使得最大长度和最小长度的差尽可能小。

输入格式

第一行两个正整数 $N,L$,表示巧克力的块数与巧克力的总长度。

第二行单调递增的 $N-1$ 个正整数,表示巧克力可以折断的位置坐标 $ x_i$。

输出格式

一个整数 $M$,表示最大和最小的巧克力的最小的差。

输入输出样例

输入 #1

8 18
3 4 5 8 10 12 15

输出 #1

2

说明/提示

对于 $20\%$ 的数据,保证 $N\le 10$.

对于 $40\%$ 的数据,保证 $N\le 100$.

对于 $60\%$ 的数据,保证 $N\le 1000$.

对于 $80\%$ 的数据,保证 $N\le 10^4$.

对于 $100\%$ 的数据,保证 $4\le N \le 2·10^5,4\le L\le 10^{15},1\le x_i\le 10^{15},x_i<x_{i+1}\; for\; 1\le i< n+2 $.

分析

显然,我们需要确定 $3$ 个点,使长度为 $L$ 的序列被切成 $4$ 段。

首先,我们考虑枚举 $3$ 个点的位置,时间复杂度大概 $O(n^3)$,是不可接受的。然后,我们考虑对暴力进行优化,枚举中间的分割点,再在中间的分割点的两边分别二分分割点的位置,时间复杂度 $O(n \log n)$,期望得分$80pts$。

经过观察,我们发现对于每一组方案的三个分割点 $left,middle,right$,一定满足 $left$ 和 $right$ 是单调不减的。对于 $left,middle,right$,我们可以看作 $0,left,middle$ 把 $[0,middle]$ 这个区间分成了两段,既然我们想要让各段长度之差尽可能的小,我们就要让 $left$ 尽可能的接近这个区间的中点,那么我们假设上一次计算已经得到了 $middle=middle-1$ 时的最优解,那么就一定满足 $left$ 比这个区间的中点更靠左。如果我们让 $left$ 向左,那么显然这种方案是更劣的。

因此,我们可以枚举 $middle$,同时对于每个 $middle$ 根据 $left$ 和 $right$ 的单调性求出答案。

代码

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n,l,ans=LONG_LONG_MAX,a[2000001];
int dif(int left,int mid,int right){
    int maxx=max(mid-left,right-mid);
    int minn=min(mid-left,right-mid);
    return maxx-minn;
}
int calc(int left,int mid,int right){
    int maxx=max(max(a[left],a[mid]-a[left]),max(a[right]-a[mid],l-a[right]));
    int minn=min(min(a[left],a[mid]-a[left]),min(a[right]-a[mid],l-a[right]));
    return maxx-minn;
}
signed main(){
    scanf("%llu%llu",&n,&l),n--;
    for(int i=1;i<=n;i++)scanf("%llu",&a[i]);
    if(a[n]!=l)a[++n]=l;
    int left=1,mid=2,right=3;
    for(;mid+2<=n;mid++){
        while(dif(0,a[left+1],a[mid])<dif(0,a[left],a[mid]))left++;
        while(dif(a[mid],a[right+1],l)<dif(a[mid],a[right],l))right++;
        ans=min(ans,calc(left,mid,right));
    }
    printf("%llu",ans);
    return 0;
}
最后修改:2021 年 07 月 20 日 03 : 02 PM
如果觉得我的文章对你有用,请随意赞赏