http://codeforces.com/contest/1435

C. Perform Easily

 

题意：6 个数，分别为 aia_i，有 n 个数的数组 bb，对每个数，选择一个 aa，得到 ci=bi−ajc_i=b_i-a_j，要使得 cc 的最大值和最小值之差最小。

尺取法

把这 6n6n 个数从小到大排列，只要一个区间满足有 n 种不同的 b，则满足条件，这时就可以和答案比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cout<<#x<<":\t"<<x
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
int a[10];
int n;
int b[N];
int L,R;
typedef pair<int,int>pii;
int m;
int ans=INF;
pii c[N];
int vis[N],cnt;
int main(){
    for(int i=1;i<=6;i++)scanf("%d",&a[i]);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    if(n==1){puts("0");return 0;}
    for(int i=1;i<=n;i++)for(int j=1;j<=6;j++){
        c[++m]=pii(b[i]-a[j],i);
    }
    sort(c+1,c+m+1);
    L=1;
    vis[c[1].second]=1;
    cnt=1;
    for(int i=2;i<=m;i++){
        vis[c[i].second]++;
        if(vis[c[i].second]==1)cnt++;
        while(vis[c[L].second]>1){
            vis[c[L].second]--;
            L++;
        }
        if(cnt==n)ans=min(ans,c[i].first-c[L].first);
    }
    printf("%d\n",ans);
    return 0;
}