文章目录
一.Problem
在糖果工厂中，有一台神秘的机器。它生产许多美味的糖果，每一个都与众不同。这个机器有一排输出槽，编号为 到 ，糖果加工完毕就会从里面出来。没有人真正知道它的工作原理，但是在每一次产品计划之前，它会打印一个列表告诉老板每个糖果会在何时从哪个槽出来。
现在，老板可以安装自动收集车在每个槽下移动，以收集掉落的糖果。当然，糖果不能掉到地上，不然就会碎裂。然而，安装自动收集车的成本极其高昂，老板想尽量少安装自动收集车。
写一个程序计算接住所有糖果需要的自动收集车的数量，它应当尽可能小。此外，你的程序还需要输出每颗糖果会被哪辆收集车接住。收集车每秒可以从一个槽移动到另一个相邻的槽。在生产过程开始前，每辆收集车可以移动到他应当收集的第一个糖果的位置。
1
≤
n
≤
100000
,
0
≤
s
i
,
t
i
≤
1000000000
1\leq n \leq 100000,0\leq s_i,t_i \leq 1000000000
1≤n≤100000,0≤si,ti≤1000000000
传送门
二.Solution
这道题目有点意思，其实就是推结论。
由题目我们可以知道若机器人能从
i
i
i到
j
j
j，那么
∣
S
j
−
S
i
∣
|S_j-S_i|
∣Sj−Si∣
≤
\leq
≤
T
j
−
T
i
T_j-T_i
Tj−Ti
=
>
T
i
−
T
j
≤
S
j
−
S
i
≤
T
j
−
T
i
=>T_i-T_j\leq S_j-S_i\leq T_j-T_i
=>Ti−Tj≤Sj−Si≤Tj−Ti
=
>
{
T
i
+
S
i
≤
T
j
+
S
i
T
i
−
S
i
≤
T
j
−
S
j
=>\left\{ \begin{aligned} T_i+S_i \leq T_j+S_i \\ T_i-S_i \leq T_j-S_j \end{aligned} \right.
=>{Ti+Si≤Tj+SiTi−Si≤Tj−Sj
于是就可以发现这是一个以
(
T
i
+
S
i
,
T
i
−
S
i
)
(T_i+S_i,T_i-S_i)
(Ti+Si,Ti−Si)为关键字的二维偏序。
什么是二位偏序呢？
我的理解就是要以两个关键字排序，那么实现就是先以一个关键字排序，再维护另一个关键字，这可以用树状数组实现。
然后考虑这道题目先按第一个关键字排序，那么就要找以第二个关键字为标准的最少有多少个上升子序列。
于是我们每次贪心地取
T
j
−
S
j
≤
T
i
−
S
i
T_j-S_j\leq T_i-S_i
Tj−Sj≤Ti−Si且
T
j
−
S
j
T_j-S_j
Tj−Sj最大的
j
j
j，这两个用同一个机器人去接，将
j
j
j更新为
i
i
i，如果找不到一个
j
j
j使得
T
j
−
S
j
≤
T
i
−
S
i
T_j-S_j\leq T_i-S_i
Tj−Sj≤Ti−Si，就需要用另一个机器人去接。
这个过程需要用
s
e
t
set
set实现，却有用数组实现的大佬(我自己就是)，这里介绍几种
s
e
t
set
set的基本操作（set常数大的一批，因为它自动排序加去重）：
- 首先有一些基本的操作，比如：
① . i n s e r t ( s t h ) .insert(sth) .insert(sth)插入
② . e r a s e ( s t h ) .erase(sth) .erase(sth)删除
③ . c o u n t ( s t h ) .count(sth) .count(sth)某个元素的个数
④ . b e g i n ( ) .begin() .begin()返回第一个元素
⑤ . e n d ( ) .end() .end()返回最后一个元素
⑥ . c l e a r ( ) .clear() .clear()清空
⑦ . e m p t y ( ) .empty() .empty()判断是否为空
⑧ . s i z e ( ) .size() .size()返回元素个数 - 然后有一个进阶操作，注意要先写出迭代器set<>::iterator it = S.操作,<>内写你定义的类型，这里的操作有：
①.lower_bound(sth)返回第一个大于或等于sth的迭代器位置
②.upper_bound(sth)返回第一个大于sth的迭代器位置
三.Code
#include <bits/stdc++.h>
using namespace std;
#define M 100005
struct node {
int s, t, id;
friend bool operator < (node a, node b){
return a.t - a.s == b.t - b.s ? (a.t + a.s) < (b.t + b.s) : (a.t - a.s < b.t - b.s);
}
}a[M];
int n, cnt;
set <node> ans;
template <class T> inline T read (T x){
x = 0; T f = 1; char c = getchar ();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar ();}
while (c >= '0' && c <= '9') {x = x * 10 + c - 48; c = getchar ();}
return x * f;
}
bool cmp (node a, node b){
return a.t + a.s == b.t + b.s ? (a.t - a.s) < (b.t - b.s) : (a.t + a.s < b.t + b.s);
}
signed main (){
freopen ("candy.in", "r", stdin);
freopen ("candy.out", "w", stdout);
n = read (1);
for (int i = 1; i <= n; i ++){
a[i].s = read (1), a[i].t = read (1);
//printf ("%d\n", a[i].t - a[i].s);
}
sort (a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i ++){
set<node>::iterator it = ans.upper_bound (a[i]);
if (it == ans.begin ())
a[i].id = ++ cnt;
else
it --, a[i].id = it -> id, ans.erase (it);
ans.insert (a[i]);
}
printf ("%d\n", cnt);
for (int i = 1; i <= n; i ++){
printf ("%d %d %d\n", a[i].s, a[i].t, a[i].id);
}
return 0;
}