CodeForces 1435C Perform Easily

十一月 04, 2020 4470

题意简述

给定一个长为 n 的序列 a ，一个长为 6 的序列 b 。你需要对每一个 i \in [1, n] 指定一个 j \in[1, 6] ，让构成的新序列 c_i = a_i - b_j 极差最小。输出这个极差。

保证 a 的最小值大于 b 的最大值。

解题思路

一个常用的套路：固定最大值求最小值。

首先扫一遍把所有可能的 c 预处理出来，并记录一下这个可能的 c 是由哪个 i 计算出来的（也就是这个 c 可能填到哪个元素），一块存到结构体里。

接下来考虑固定最大值。我们枚举一个 k 表示固定某个 c_k 为最大值，那么接下来我们的任务就是：对于每一个 i ，为它指定一个可能的 c_i 使得 c_i < c_k 且 \min c_i 最大，并获取这个 \min c_i 。

这里面有四个问题和一个要点：

  1. 每一个 i ，也就是要求序列 c 的每一位都必须有得选；
  2. c_i < c_k ，也就是要求能选的数都得小于 c_k ；
  3. \min c_i 最大，也就是要求每个元素都尽量大。
  4. 获取这个 \min c_i ，也就是要求可以快速求出选完的序列 c 的全局最小值；
  5. 枚举的是“某个” c_k ，也就是意味着 c 序列中第 k 个元素可以有多个取值。

对于这四个问题，我们分别可以这样解决：

  1. 记录一下当前有多少个元素有得选，或者通过一些奇怪的方法让答案更新不了；
  2. 将存的结构体按照 c 升序排序，这样可以保证所有可选的 c 结构体下标都在 k 前面；
  3. 选的时候总是选最大值，如果一个元素位置能选的 c 有更大的就不用再更新了；
  4. 快速求全局最小值。

可以发现，这个东西可以使用线段树进行维护！

考虑对 c 序列建立线段树。令 d_i 表示当前 c_i 能选的最大值，使用线段树维护 d_i 的全局最小值，支持单点的取最大值，就可以实现上述操作。

代码实现

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;
#define forall(G,u) for (int i_ = 0, __for_siz__ = (int) G[u].size(); i_ < __for_siz__; ++i_) 
#define all(x) (x).begin(), (x).end()

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

std::vector<int> price;
std::vector<int> dest;

const int MAXN = 100000 + 10;
const long long int INF = 0x3f3f3f3f3f3f3f3f;

struct Node {
    long long int id, x;
    Node(int _i = 0, long long int _x = 0) : id(_i), x(_x) {}
    bool operator < (const Node &th) const {
        return x < th.x;
    }
} nodes[MAXN * 6]; int cnt = 0;

int n, bm;

namespace SegtTree {
    long long int minn[MAXN << 2];
    
    #define lson (p << 1)
    #define rson (p << 1 | 1)
    void Update(int p) {
        minn[p] = std::min(minn[lson], minn[rson]);
    }

    void buildTree(int p, int l, int r) {
        // 一个很 nb 的操作：如果这个序列还有没填的地方，
        // 那么值查出来都是 -INF，就没法更新答案
        if (l == r) return (void) (minn[p] = -INF);
        int mid = (l + r) >> 1;
        buildTree(lson, l, mid); buildTree(rson, mid + 1, r);
        Update(p);
    }

    void Modify(int p, int l, int r, int pos, long long int k) {
        // 本来这里应该是 minn[p] = std::max(minn[p], k)
        // 但是要修改的值都已经升序排序了，当前的 k 一定比 minn[p] 大
        // 就没必要取 max 了，直接覆盖即可
        if (l == r) return (void) (minn[p] = k);
        int mid = (l + r) >> 1;
        if (pos <= mid) Modify(lson, l, mid, pos, k);
        else Modify(rson, mid + 1, r, pos, k);
        Update(p);
    }

    long long int Query() { return minn[1]; }
}

int main() {
    bm = 6;
    for (int i = 1; i <= bm; ++i) price.push_back(read());
    n = read();
    for (int i = 1; i <= n; ++i) dest.push_back(read());
    std::sort(all(price)); price.erase(std::unique(all(price)), price.end());
    std::sort(all(dest)); dest.erase(std::unique(all(dest)), dest.end());
    n = (int) dest.size(); bm = (int) price.size();
    SegtTree::buildTree(1, 1, n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < bm; ++j) {
            nodes[++cnt] = Node(i + 1, dest[i] - price[j]);
        }
    } std::sort(nodes + 1, nodes + 1 + cnt);
    long long int ans = INF;
    for (int i = 1; i <= cnt; ++i) {
        SegtTree::Modify(1, 1, n, nodes[i].id, nodes[i].x);
        // 固定最大值为 nodes[i].x，求其他所有最大值中的最小值
        // 第一个是要保证所有位置都有值
        // 第二个是要保证所有位置存的都是最大值
        ans = std::min(ans, nodes[i].x - SegtTree::Query());
    } printf("%lld\n", ans);
    return 0;
}