前一段时间我做的一道题目，感觉挺不错的，愿与大家分享。

题目简述：
在一条数轴上第ti秒会在si处掉落一个糖果，共n个，每个机器人每秒可静止不动或移动到相邻位置，求捡到所有糖果的最少机器人数。
n≤100000。

关键字：
线段树/二分查找（类似LIS）

算法描述：
以时间为x轴，位置为y轴建系，可以发现对于一个点，能到达它的机器人肯定在两条斜率k=±1的直线在它之前所夹之角的范围内，故将坐标系旋转45°可将问题转化为：平面上给的一些点，求至少要几条只能向右上走的路径可以覆盖所有点。
对于转化后的问题，可以按照将y坐标离散化（相同的y坐标按照x从小到大离散化为不同的值），然后按照x、y为第一、第二关键字从小到大扫描，每次在线段树中查询是否有y坐标当前点的点，如果有，取出y坐标最大点（并从线段树中删除），与当前点连成一条路径；如果没有，则新建一条路径。最后将当前点插入线段树。这样贪心可以保证最优（类似与NOIP《导弹拦截》第二问的贪心解法）。
通过观察可以发现，如果可以取出一个点，那么插入新的点后线段树所维护的序列中数的相对位置并没有改变，而无法取出时则必然插入在序列的头部，所以可以用一个线性表维护后二分查找，而不用线段树。

解题心得&收获：
对于题目的分析和问题的转化，旋转坐标系是一种在信息奥赛中很常见的思路，常见的题型有曼哈顿距离（由于在给定的曼哈顿距离内的点集是菱形，旋转45°后就变成了和坐标轴平行的矩形，就可以使用一些数据结构和扫描线类的方法维护）。
问题所具有的一些特殊的性质可以用来简化解法（如本题中用线性表+二分代替线段树），而不是直接就暴力用高级数据结构解决。

My Code（C++）：

/*
Title: candy
Author: ltl
*/

#include <iostream>
#include <memory.h>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

#define InputFileName        "XXXXXXXX"
#define OutputFileName        "candy.out"

using namespace std;

const int MaxN = 110000;

int n, Data[MaxN*5], Ans;
struct TVertex
{
    int x, y, Orix, Oriy, Num, Wagon;
}a[MaxN], b[MaxN];

inline bool cmpx(TVertex a, TVertex b)
{
    return a.x < b.x || a.x == b.x && a.y < b.y;
}

inline bool cmpy(TVertex a, TVertex b)
{
    return a.y < b.y || a.y == b.y && a.x < b.x;
}

inline bool cmpNum(TVertex a, TVertex b)
{
    return a.Num < b.Num;
}

inline int Min(const int a, const int b)
{
    return a < b ? a : b;
}

inline int Max(const int a, const int b)
{
    return a > b ? a : b;
}

void Init()
{
    scanf("%d", &n);
    for (int i = 1; (a[i].Num = i) <= n; ++i)
        scanf("%d%d", &a[i].y, &a[i].x);
    sort(a+1, a+n+1, cmpx);
    int MaxYX = -0x7FFFFFFF, MinXY = 0x7FFFFFFF;
    for (int i = 1; i <= n; ++i)
    {
        MaxYX = Max(MaxYX, a[i].y-a[i].x);
        MinXY = Min(MinXY, a[i].x+a[i].y);
    }
    for (int i = 1; i <= n; ++i)
    {
        b[i].x = MaxYX-(a[i].y-a[i].x);
        b[i].y = a[i].x+a[i].y-MinXY;
        b[i].Orix = a[i].x;
        b[i].Oriy = a[i].y;
        b[i].Num = a[i].Num;
    }
    sort(b+1, b+n+1, cmpy);
    for (int i = 1; i <= n; ++i)
        b[i].y = i;
    sort(b+1, b+n+1, cmpx);
}

void Insert(const int t, const int l, const int r, const int p, const int k)
{
    if (l == r)
    {
        Data[t] = k;
        return;
    }
    const int mid = l+r >> 1;
    if (p <= mid)
        Insert(t << 1, l, mid, p, k);
    else
        Insert((t << 1)+1, mid+1, r, p, k);
    Data[t] = Max(Data[t << 1], Data[(t << 1)+1]);
}

int Find(const int t, const int l, const int r, const int p)
{
    if (p >= r)
        return Data[t];
    const int mid = l+r >> 1;
    int Res = Find(t << 1, l, mid, p);
    if (p > mid)
        Res = Max(Res, Find((t << 1)+1, mid+1, r, p));
    return Res;
}

void Print()
{
    printf("%d\n", Ans);
    for (int i = 1; i <= n; ++i)
        printf("%d %d %d\n", b[i].Oriy, b[i].Orix, b[i].Wagon);
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen(InputFileName, "r", stdin);
    freopen(OutputFileName, "w", stdout);
    #endif
    Init();
    for (int i = 1, p; i <= n; ++i)
    {
        p = Find(1, 1, n, b[i].y);
        if (p)
        {
            Insert(1, 1, n, p, 0);
            b[i].Wagon = b[p].Wagon;
        }
        else
            b[i].Wagon = ++Ans;
        Insert(1, 1, n, b[i].y, b[i].y);
    }
    sort(b+1, b+n+1, cmpNum);
    Print();
    return 0;
}


题目来源：
BOI2009