题目解析
我怎么连拦截导弹都看不出来喏
就是，考虑同一台机器先后接到两个糖果(i ,j)的话，需要满足这个条件：(T_j-T_i≥|S_j-S_i|)
这个绝对值很丑，所以我们把它拆掉。
绝对值拆开的话，我们不知道具体正负，但是没关系，它们两个肯定一正一负，所以我们加双保险：
(T_j-T_i≥S_j-S_i)
(T_j-T_i≥S_i-S_j)
老套路了，我们移项，把同一个糖果的参数放在一起：
(T_j-S_j≥T_i-S_i)
(T_j+S_j≥T_i+S_i)
那么这就变成了一个二维偏序，我们可以把其中一维排序，然后对另一维做拦截导弹：贪心地用尽量大的小于等于它自己的前面的一个机器，这个可以用(set)维护。
(set)默认按(pair)的第一关键字排序。
呃，我还记错了(lower\_bound)，我以为它是查第一个小于等于的数，实际上是第一个大于等于的数；而(upper\_bound)是第一个大于的数。
►Code View
#include<cstdio>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
#define N 100005
#define MOD 998244353
#define INF 0x3f3f3f3f3f3f3f3f
#define LL long long
LL rd()
{
LL x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return f*x;
}
int n;
struct node{
int s,t,id,w;
}c[N];
int cnt;
set<pair<int,int> > s;
bool cmp(node p,node q)
{
if(p.t-p.s==q.t-q.s) return p.t+p.s<q.t+q.s;
return p.t-p.s<q.t-q.s;
}
bool cmp2(node p,node q)
{
return p.id<q.id;
}
int main()
{
n=rd();
for(int i=1;i<=n;i++)
c[i].s=rd(),c[i].t=rd(),c[i].id=i;
sort(c+1,c+n+1,cmp);
for(int i=1;i<=n;i++)
{
int tmp=-(c[i].s+c[i].t);
//lower_bound 是找第一个大于等于它的元素 而我们是要找第一个小于等于的元素
//所以取个反 就可以找第一个小于等于的元素喏
set<pair<int,int> >::iterator it=s.lower_bound(make_pair(tmp,0));
if(it==s.end())
{
cnt++;
s.insert(make_pair(tmp,cnt));
c[i].w=cnt;
}
else
{
c[i].w=it->second;
s.erase(it);
s.insert(make_pair(tmp,c[i].w));
}
}
sort(c+1,c+n+1,cmp2);
printf("%d
",cnt);
for(int i=1;i<=n;i++)
printf("%d %d %d
",c[i].s,c[i].t,c[i].w);
return 0;
}