[JOI 2023 Final] Advertisement 2 题解

手机

南亚新材（688519）：8月14日北向资金增持8.84万股

金博股份：目前公司研发的Ⅳ型储氢瓶正在开展试制工作，预计2024年完成开发，

家电

[JOI 2023 Final] Advertisement 2 题解

2023-08-15 11:53:16 来源：博客园

(资料图)

题解

JOI 王国有 \(N\) 位居民，从 \(1\) 到 \(N\) 编号。居民 \(i\)（\(1\le i\le N\)）居住在数轴上坐标 \(X_i\) 处，其影响力为 \(E_i\)。同一个坐标可能住了多于一位居民。居民的影响力越高，广告效应也越高，但买书也越谨慎。

Rie 出版了一本关于信息学的书。为了让更多人购买这本书，她可以给一些居民送书。如果她给居民 \(i\)（\(1\le i\le N\)）送了一本书，除了居民 \(i\) 将得到一本 Rie 的书外，在还没有得到这本书的居民中，每一个满足以下条件的居民 \(j\)（\(1\le j\le N\)）都会购买这本书：

居民 \(i\) 和居民 \(j\) 在数轴上的距离小于或等于 \(E_i - E_j\)。换句话说，\(|X_i - X_j| \le E_i - E_j\) 成立。

如果所有的居民都读了 Rie 的书，信息学竞赛将得到极大的认可。请写一个程序，计算 Rie 最少将书赠送给多少位居民，就可以让 JOI 王国的所有居民都会得到 Rie 的书。

题解

考虑转化题目中的限制式

\[\left\lvert X_i - X_j\right\rvert \le E_i - E_j\]

首先拆开绝对值

\[X_i - X_j \le E_i - E_j \land X_j - X_i \le E_i - E_j\]

接下来移项

\[E_j - X_j \le E_i + X_i \land X_j + E_j \le E_i + X_i\]

考虑其几何意义，对于第 \(i\) 个人 \(\left(E_i, X_i\right)\)，将 \(E_i - X_i\) 看作横坐标，将 \(E_i + X_i\) 看作纵坐标。将点 \(\left(E_i - X_i, E_i + X_i\right)\) 放到笛卡尔坐标系上，再结合限制式可以发现会受这个人影响的对应点处于该点和原点构成的矩形内。

考虑用尽可能少的点和原点组成的举行覆盖所有点，可以发现最终答案的断点一定是纵坐标随横坐标递增而递减的，使用单调栈维护即可。

Code

#include typedef int valueType;typedef std::pair ValuePair;typedef std::vector PairVector;typedef std::stack Stack;int main() {    valueType N;    std::cin >> N;    PairVector source(N);    for (auto &iter: source) {        valueType X, E;        std::cin >> X >> E;        iter = std::make_pair(E - X, E + X);    }    std::sort(source.begin(), source.end());    Stack stack;    for (auto const &iter: source) {        while (!stack.empty() && stack.top().second <= iter.second)            stack.pop();        stack.push(iter);    }    std::cout << stack.size() << std::endl;    return 0;}

关键词：