DDOSvoid's Blog

CF 1435C Perform Easily

发表于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/contest/1435/problem/C

Solution

先来考虑一个贪心，首先将序列和弦都按从小到大排好序

我们假设只有两根弦，那么最终答案显然是将序列分成两份，左边序列减第一根弦，右边序列减第二根弦

可以猜测这个结论可以推广到有六根弦的情况

我们注意观察这六段，能够注意到每一段贡献的最小值一定是段首

所以我们枚举最小值，在保证段首贡献的最小值不小于我们枚举的最小值的情况下，我们只需要使每个数都减掉较大的弦

等价于我们让每一段的段首尽可能靠左，这个东西可以直接二分一下

时间复杂度 $O(6n\log n)$

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
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cstdlib> 
#define maxn 100010
#define ll long long
#define pb push_back
#define cn const node
#define cQ const Queue
#define gc getchar
#define INF 1000000000
using namespace std;
 
int read() {
    int x = 0; char c = gc();
    while (!isdigit(c)) c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return x;
}
 
int n, a[7], b[maxn], c[maxn * 6], c1;
 
int Ans = INF; 
int main() {
    for (int i = 1; i <= 6; ++i) cin >> a[i];
    sort(a + 1, a + 7); 
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> b[i];
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= 6; ++j) c[++c1] = b[i] - a[j];
    for (int i = 1; i <= c1; ++i) {
        int mx = 0, p = 1; if (c[i] > b[1] - a[1]) continue; 
        for (int j = 2; j <= 6; ++j) {
            int l = p + 1, r = n, mid, ans = n + 1; 
            while (l <= r) {
                mid = l + r >> 1;
                if (b[mid] - a[j] >= c[i]) ans = mid, r = mid - 1;
                else l = mid + 1;
            } mx = max(b[ans - 1] - a[j - 1], mx); 
        } mx = max(mx, b[n] - a[6]);
        Ans = min(Ans, mx - c[i]); 
    } cout << Ans << endl; 
    return 0;
}

当然还有更加简单的做法

我们直接把 $6n$ 个数排序，然后枚举最小值双指针即可

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
40
41
42
43
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define maxn 100010
#define pb push_back
#define cn const node
#define INF 1000000000
using namespace std;

int n, a[maxn], b[7];
struct node {
    int k, v;

    node() {}
    node(int _k, int _v ) { k = _k; v = _v; }

    friend bool operator < (cn &u, cn &v) { return u.v < v.v; } 
} A[maxn * 6]; int c1;

int cnt[maxn], sum;
inline void add(int x) { if (++cnt[x] == 1) ++sum; } 

inline void del(int x) { if (--cnt[x] == 0) --sum; } 

int main() {
    for (int i = 1; i <= 6; ++i) cin >> b[i];
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= 6; ++j) A[++c1] = node(i, a[i] - b[j]);
    sort(A + 1, A + c1 + 1); int ans = INF, j = 1;
    for (int i = 1; i <= c1; ++i) {
        while (sum < n && j <= c1) add(A[j++].k); 
        if (sum < n) break;
        ans = min(ans, A[j - 1].v - A[i].v);
        del(A[i].k); 
    } cout << ans << endl; 
    return 0;
    
}