题目地址
http://codeforces.com/contest/1435/problem/C
大致题意
有一个长度为6的数组a，代表每根弦的初始值。
有另外一个数组b，代表需要弹奏的每个音符。
每根琴弦的琴格从1开始。（在弹吉他里应该叫x品吧）
如果我要弹音符$b_i$,找到$x$满足$b_i=x+a_j $则可以按琴弦j的琴格$x$来弹出这个音。（$j$弦$x$品）
问怎么弹所有音符可以让最大的$x$和最小的$x$之间的差值最少？
题目思路
方法1：二分
方法来自大佬的博客：https://www.cnblogs.com/acceptedzhs/p/13876630.html
先对ab两个数组进行排序并且去重（这里a的去重是必要的，并不仅仅是为了速度）
设a的长度为m，b的长度为n，我们枚举n和m，复杂度$O(n) $
即对音符和琴弦进行枚举，$minx = b_j - a_i $,设$minx$就是之后最小的琴格，比$minx $还小的就是不可行的了。
我们定义”最悲惨的音符”是那些“刚好可以使用琴弦a[k]却无法使用琴弦$a_{k-1} $中的音符”里最大的。
显然这样的音符最多只有$m-1 $个。（之前去重就是因为这里，不然$a_k = a_{k-1} $就出错了。
如果$b_1 < minx + a_1 $,则不可能存在”能使用$a_1 $但无法使用$a_2 $的音符”，对于这种情况我们直接判定这个$minx$不合法，跳过。
琴格的最大位置一定在这些“最悲惨的音符”和最大的那个音符中产生。
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
template<class T>inline void read(T &x){x=0;char o,f=1;while(o=getchar(),o<48)if(o==45)f=-f;do x=(x<<3)+(x<<1)+(o^48);while(o=getchar(),o>47);x*=f;}
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=b;i--)
#define mkp make_pair
#define ft first
#define sd second
#define log(x) (31-__builtin_clz(x))
#define INF 0x3f3f3f3f
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll gcd(ll a,ll b){ while(b^=a^=b^=a%=b); return a; }
//#define INF 0x7fffffff
const int MAXN = 1e5+5;
ll a[8];
ll b[MAXN];
int n;
void solve(){
int m = 6;
rep(i,1,m) cin>>a[i];
sort(a+1,a+1+m);
m = unique(a+1,a+1+m)-a-1;
cin>>n;
rep(i,1,n) cin>>b[i];
sort(b+1,b+1+n);
n = unique(b+1,b+1+n)-b-1;
//读入两个数组，排序去重
ll minx,maxx,minn = 1ll<<62;
rep(i,1,n){
rep(j,1,m){
maxx = 0;
minx = b[i]-a[j];
if(b[1]-a[1]<minx) continue;
rep(k,1,m){
//注意琴格从1开始
//b[?]-a[k]>=minx 变形 b[?]>=minx+a[k]
int px = lower_bound(b+1,b+1+n,minx+a[k])-b-1;
//找到最后一个可以用a[k-1]但一定用不了a[k]的
maxx = max(b[px]-a[k-1],maxx);
}
repb(k,m,1){
if(b[n]-a[k]>=minx){//和音符中的最大值进行比较,并且找一根尽可能大的琴弦
maxx = max(maxx,b[n]-a[k]);
break;
}
}
minn = min(maxx-minx,minn);
}
}
cout<<minn<<endl;
}
int main(){
solve();
}方法2：集合
来自另一个大佬的博客：https://blog.csdn.net/I_have_a_world/article/details/109287448
我更喜欢这第二种方法，复杂度上应该都是$O(nlogn)$的。但是这个方法真的挺简洁易懂的。
两个数组可以不去重,但是去重的话效率应该会更高。
搞一个in[MAXN]数组，记录当前这个音符所在的弦。
设排序去重后有n个音符，m个琴弦。
一开始每个音符都在弦m上，用pair<ll,ll>来记录，分别记录$b_i - a_{in[i]} $和编号$i$。
把这些二元组都存在集合set里，然后每次取出first最小的(即$b_i - a_{in[i]} $)最大的元素i，和集合中first最大的做差。在这些数值中找最小值。
这样以后，把最小的i对应的in[i]–，即让他变得更大再加入集合。
重复这些步骤直到最小的元素也是用的1弦。为什么？因为这时候其他弦如果再往下换弦，也只能使$b_i - a_{in[i]} $变得更大，使最大-最小的值变大或者不变，所以到这里就没必要继续往下了。
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=b;i--)
#define mkp make_pair
#define ft first
#define sd second
typedef pair<ll,ll> pll;
const int MAXN = 1e5+5;
ll a[8];
ll b[MAXN];
int in[MAXN];
int n;
set<pll>st;
void solve(){
int m = 6;
rep(i,1,m) cin>>a[i];
sort(a+1,a+1+m);
m = unique(a+1,a+1+m)-a-1;
cin>>n;
rep(i,1,n) cin>>b[i];
sort(b+1,b+1+n);
n = unique(b+1,b+1+n)-b-1;
//这里其实没太大必要去重，但是我想了一下还是去重了
rep(i,1,n){
in[i] = m;
st.insert(mkp(b[i]-a[m],(ll)i));//一开始都是用m弦弹的
}
ll minn = st.rbegin()->ft-st.begin()->ft;
while(1){
pll now = *st.begin();
st.erase(st.begin());//这边的参数是迭代器,这样删复杂度更小
if(in[now.sd]==1) break;
//如果最小的都是1,那么其他的音符换弦也不可能让结果更小了,因为往下换只会让bi-aj更大
in[now.sd]--;//每次换成更小的弦
st.insert(mkp(b[now.sd]-a[in[now.sd]],now.sd));
minn = min(minn,st.rbegin()->ft-st.begin()->ft);
}
cout<<minn<<endl;
}
int main(){
solve();
}
