题解 CF1413C 【Perform Easily】
Zesty_Fox
2020-10-27 07:37:18
~~毒瘤C题，考场卡我1个小时~~
前往博客，食用效果更佳：[点这里](https://www.cnblogs.com/acceptedzhs/p/13876630.html)
首先，这道题难点在哪里？**它的最大值与最小值都是浮动的**。
怎么办？**把最小/最大值固定！**
以把最小值固定为例，我们枚举每个音符，并枚举它使用哪条琴弦，将它此时的位置**强制**其作为最小值（设为$minx$）。
同时，我们令其他音符**不作为最小值**，即其他的音符的位置**不能**小于最小值。
接下来，我们只需计算每个音符的最小位置（但不小于最小值），在这些音符中取 $\max$ 即可。
直接的想法是枚举其他的所有音符，寻找满足 $b_i-a_j \ge minx$ 最大 $a_j$ （此时 $b_i-a_j$ 最小）。
很明显，这样做是 $O(n)$ 的。然而，我们要枚举 $6n$ 个最小值，时间复杂度为$O(n^2)$ （把常数项省掉了）…
略加思考，我们发现并不是所有的音符都要枚举一遍。我们把$a、b$数组分别从小到大排序，并把$a$数组去重（原因后面讲），那么**最悲惨的音符**~~（雾）~~ 肯定是**那些可以用 $a_{j-1}$ 的琴弦，但正好用不了 $a_j$ 的琴弦的音符**中**最大**的一个。当然，如果存在音符连 $a_1$ 都用不了，直接判定**当前最小值不合法**，并枚举下一个最小值。
举个例子：$a$数组为 $[1,3,5]$ （去重以后），$b$数组为 $[4,5,6,6,7]$，$minx$为$3$。
那么，$5、7$是最悲惨的音符，因为$5$是可以用琴弦$a_1$但用不了琴弦$a_2$（有$4、5$两个音符）中最大的音符，$7$是可以用琴弦$a_2$但用不了琴弦$a_3$中最大的音符。显然，最大的位置将在最悲惨的音符中产生。
由于我们对 $b$ 数组排过序，因此对每一条琴弦，直接二分查找最大的 $b_i$ ，使 $b_i-a_j < minx$ 即可。
于是，我们只要找到这些音符即可。这些音符最多不超过$6$个。时间复杂度 $O(n \log n)$ 。
最后说一句，为什么$a$要去重？因为我们要找可以用 $a_{j-1}$ 的琴弦但用不了 $a_j$ 的琴弦的音符，如果存在重复，即 $a_{j-1}=a_j$ ，则可能这个音符 $a_{j-1}$ 的琴弦、 $a_j$ 的琴弦都用不了，明显不符。
$Code:$
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
ll a[10],n,b[100010],pos[10],cnt;
ll ans=1e18;
int main(){
for(int i=1;i<=6;i++) scanf("%lld",&a[i]);
sort(a+1,a+7);cnt=unique(a+1,a+7)-a-1;//去重
cin>>n;
for(int j=1;j<=n;j++) scanf("%lld",&b[j]);
sort(b+1,b+n+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=cnt;j++){
ll minx=b[i]-a[j],maxn=0,last=0; //枚举minx
if(b[1]-a[1]<minx) goto fail;
for(int k=2;k<=cnt;k++){
last=lower_bound(b+last+1,b+n+1,minx+a[k])-b-1;//二分查找
maxn=max(maxn,b[last]-a[k-1]);//更新最大位置
}
for(int k=cnt;k>=1;k--){
if(b[n]-a[k]>=minx){
maxn=max(maxn,b[n]-a[k]); //最大的音符特殊处理一下
break;
}
}
ans=min(ans,maxn-minx);//更新答案
fail:;
}
}
cout<<ans<<endl;
return 0;
}
```