( ext{Description})
【题目描述】
在糖果厂里，有一台生产糖果的机器。机器有一排输出口，编号从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)的机器人接住。
【样例1输入】
5
1 1
2 3
1 5
3 4
2 6
【样例1输出】
2
1 1 1
2 3 1
1 5 2
3 4 1
2 6 2
【样例 2】
见下发文件下的 candy/candy2.in 与 candy/candy2.out
【数据范围与约束】
只输出任务1的正确答案， 将获得该测试点50%的得分。
任务2的方案不唯一，输出任何一个合法方案即可。
对100%的数据, (0 leq s_i, t_i leq 10^9)
| 测试点编号 | n | 特殊性质 |
|---|---|---|
| 1~2 | $ leq 10^2$ | (w leq 4) |
| 3~6 | (leq 8 imes 10^3) | |
| 7~10 | (leq 10^5) |
( ext{Solution})
( ext{Code})
#include <cstdio>
#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar('-'),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}
#include <set>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
struct node {
int s,t,i;
friend bool operator < (node x,node y) {
return x.t+x.s<y.t+y.s;
}
} a[maxn];
int n,tot;
set <node> st;
set <node> :: iterator it;
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);
}
int main() {
freopen("candy.in","r",stdin); freopen("candy.out","w",stdout);
n=read(9);
rep(i,1,n) a[i].s=read(9),a[i].t=read(9);
sort(a+1,a+n+1,cmp);
rep(i,1,n) {
it=st.upper_bound(a[i]);
if(it==st.begin()) a[i].i=++tot;
else --it,a[i].i=it->i,st.erase(it);
st.insert(a[i]);
}
print(tot,'
');
rep(i,1,n) printf("%d %d %d
",a[i].s,a[i].t,a[i].i);
return 0;
}