【题解】Fair

题目描述

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

​ 蛤蟆先生和他的三个兄弟得到了一条长度为 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

© 允许规范转载