acd - 1216 - Beautiful People（二維LIS）

acd - 1216 - Beautiful People（二維LIS）

題意：一個人有兩個屬性S, B(1 ≤ Si, Bi ≤ 10^9)，當兩個人的這兩個屬性滿足 S1 < S2 && B1 < B2 或者 S1 > S2 && B1 > B2 時，這兩個人不會討厭對方。現給出 N 個人(2 ≤ N ≤ 100 000)的屬性，求最多能有多少個人，他們之間任意兩人都不會討厭對方。

——>>容易想到是一個二維的LIS模型。。

二維降一維，控制其中一維遞增，對另一維求LIS。。（主要是在排序的時候，讓第一維從小到大排，第二維從大到小排，那麼，排序後對第二維求LIS的結果肯定不會出現其中的元素對應的第一維是相同的，因為相同的第一維對應的第二維是遞減的，而對第二維求LIS是嚴格遞增的。。）

#include 
#include 
#include 

using std::sort;
using std::lower_bound;

const int MAXN = 100000 + 10;
const int INF = 0x3f3f3f3f;

struct PERSON
{
    int id;
    int S;
    int B;

    bool operator < (const PERSON& e) const
    {
        return S < e.S || (S == e.S && B > e.B);
    }
} person[MAXN];

int N;
int buf[MAXN];
int lis[MAXN], who[MAXN], fa[MAXN], cnt;

int LIS()
{
    int ret = 1;

    memset(lis, 0x3f, sizeof(lis));
    memset(fa, -1, sizeof(fa));
    who[0] = -1;
    for (int i = 1; i <= N; ++i)
    {
        int id = lower_bound(lis + 1, lis + 1 + N, buf[i]) - lis;
        lis[id] = buf[i];
        who[id] = i;
        fa[i] = who[id - 1];
        if (id > ret)
        {
            ret = id;
        }
    }

    return ret;
}

void Read()
{
    for (int i = 1; i <= N; ++i)
    {
        scanf(%d%d, &person[i].S, &person[i].B);
        person[i].id = i;
    }
}

void Init()
{
    sort(person + 1, person + 1 + N);
    for (int i = 1; i <= N; ++i)
    {
        buf[i] = person[i].B;
    }
}

void Output(int x)
{
    if (fa[x] == -1)
    {
        printf(%d, person[x].id);
        return;
    }
    Output(fa[x]);
    printf( %d, person[x].id);
}

void Solve()
{
    cnt = LIS();
    printf(%d
, cnt);
    Output(who[cnt]);
    puts();
}

int main()
{
    while (scanf(%d, &N) == 1)
    {
        Read();
        Init();
        Solve();
    }

    return 0;
}