题目

题目背景

在糖果厂里，有一台生产糖果的机器。机器有一排输出口，编号从 \(1\) 到 \(n\)。一颗糖果生产好后就会从某个输出口掉出来。
糖果机在开始生产之前，它会打印一张列表，告诉工厂老板，每颗糖果何时以及从哪个插槽掉出来。
工厂老板可以在输出槽下方安装移动的机器人，以抓住掉落的糖果。
任何糖果都不能掉在地板。机器人以每秒移动一槽宽度的速度运行。 在生产过程开始之前，每个机器人可以安排到抓起第一个糖果的插槽位置。
由于机器人很昂贵，老板希望安装尽可能少的机器人。
编写一个程序，完成以下两个子任务。

子任务 \(1\)：计算接住所有糖果所需机器人的最小数量。

子任务 \(2\)：输出哪个机器人应该接住哪个糖果。

输入格式

第 \(1\) 行包含一个整数 \(n\)，表示生产的糖果数。
接下来 \(n\) 行，每行包含一对整数 \(s_i, t_i\)，分别表示第 \(i\) 颗糖果的输出槽编号和完成时刻。 每对 \((s_i, t_i)\) 是唯一的。

输出格式

输出的第一行仅包含一个整数 \(w\)，表示接住所有糖果所需的机器人最小数量。机器人编号从 \(1\) 到 \(w\).

接下来 \(n\) 行，每行 \(3\) 个整数 \((s_i, t_i, w_i)\)，表示 \(t_i\) 时刻，由输出槽 \(s_i\) 产出的糖果由编号为 \(w_i\) 的机器人接住.

数据范围

对 \(100\%\) 的数据, \(0 \leq s_i, t_i \leq 10^9\)

测试点编号	n	特殊性质
1~2	$ \leq 10^2$	\(w \leq 4\)
3~6	\(\leq 8 \times 10^3\)
7~10	\(\leq 10^5\)

每个测试点若只输出子任务 \(1\) 的答案，可得到该测试点 \(50\%\) 的得分。

题解

导弹拦截都看不出来了 = A=.

考虑一个机器人在接完 \(i\) 糖果之后还可以去接 \(j\) 糖果需要满足的条件，显然是这个东西：

\[T_j-T_i\ge |S_j-S_i| \]

分两种情况：

\(1^\circ\).如果 \(S_j\ge S_i\)，那么必须得满足 \(T_j-T_i\ge S_j-S_i\)，显然地，如果前者满足，亦满足 \(T_j-T_i\ge S_i-S_j\).

\(2^\circ\).如果 \(S_j< S_i\)，那么必须得满足 \(T_j-T_i\ge S_i-S_j\)，显然地，如果前者满足，亦满足 \(T_j-T_i\ge S_j-S_i\).

那么上面两种情况可以同意一下，即如果 \(i\) 糖果之后去接 \(j\) 糖果，必须满足：

\[\begin{cases} T_j-T_i\ge S_i-S_j \\ T_j-T_i\ge S_j-S_i \end{cases} \]

我们整理一下这个柿子，得到这个约束条件

显然，以 \((T_i-S_i,T_i+S_i)\) 为关键字的二维偏序，将第一维排序之后在第二维上做导弹拦截即可.

代码

#include<bits/stdc++.h>
using namespace std;
namespace IO{
	#define rep(i,l,r) for(int i=l,i##_end_=r;i<=i##_end_;++i)
	#define fep(i,l,r) for(int i=l,i##_end_=r;i>=i##_end_;--i)
	#define fi first
	#define se second
	#define Endl putchar('\n')
    #define writc(x,c) fwrit(x),putchar(c)
	typedef long long ll;
	typedef pair<int,int> pii;
	template<class T>inline T Max(const T x,const T y){return x<y?y:x;}
	template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
	template<class T>inline T fab(const T x){return x<0?-x:x;}
	template<class T>inline void getMax(T& x,const T y){x=Max(x,y);}
	template<class T>inline void getMin(T& x,const T y){x=Min(x,y);}
	template<class T>T gcd(const T x,const T y){return y?gcd(y,x%y):x;}
	template<class T>inline T readin(T x){
		x=0;int f=0;char c;
		while((c=getchar())<'0' || '9'<c)if(c=='-')f=1;
		for(x=(c^48);'0'<=(c=getchar()) && c<='9';x=(x<<1)+(x<<3)+(c^48));
		return f?-x:x;
	}
    template<class T>void fwrit(const T x){
        if(x<0)return putchar('-'),fwrit(-x);
        if(x>9)fwrit(x/10);putchar(x%10^48);
    }
}
using namespace IO;

const int maxn=1e5;

int t[maxn+5],s[maxn+5];

struct node{int a,b,i;
    inline int operator <(const node rhs)const{
        return a==rhs.a?b<rhs.b:a<rhs.a;
    }
}p[maxn+5];
int n;

inline void Init(){
    n=readin(1);
    rep(i,1,n){
        s[i]=readin(1),t[i]=readin(1);
        p[i]=node{t[i]-s[i],t[i]+s[i],i};
    }sort(p+1,p+n+1);
}

struct ans_info{
    int s,t,w;
}ans[maxn+5];

int q[maxn+5],ed;

inline int find(const int x){
    if(!ed || q[ed]>x)return -1;
    int l=1,r=ed,mid,ret;
    while(l<=r){
        mid=l+r>>1;
        if(q[mid]<=x)ret=mid,r=mid-1;
        else l=mid+1;
    }return q[ret]<=x?ret:-1;
}
signed main(){
    // freopen("candy.in","r",stdin);
    // freopen("candy.out","w",stdout);
    Init();
    rep(i,1,n){
        int x=find(p[i].b);
        int id=p[i].i;
        if(x==-1){
            q[++ed]=p[i].b;
            ans[i]=ans_info{s[id],t[id],ed};
        }else{
            q[x]=p[i].b;
            ans[i]=ans_info{s[id],t[id],x};
        }
    }writc(ed,'\n');
    rep(i,1,n)writc(ans[i].s,' '),writc(ans[i].t,' '),writc(ans[i].w,'\n');
	return 0;
}