ZOJ 2319 Beautiful People

LIS。先按S降序升序再按B降序排序（如果B不按降序排序的话就会覆盖掉正解），然后再对B用O(nlog(n))的LIS求解就可以了。用d数组标记每个元素在上升序列中的位置，然后根据d倒着找id就可以了。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<fstream>

#include<sstream>

#include<cstdlib>

#include<vector>

#include<string>

#include<cstdio>

#include<bitset>

#include<queue>

#include<stack>

#include<cmath>

#include<map>

#include<set>

#define FF(i, a, b) for(int i=a; i<b; i++)

#define FD(i, a, b) for(int i=a; i>=b; i--)

#define REP(i, n) for(int i=0; i<n; i++)

#define CLR(a, b) memset(a, b, sizeof(a))

#define debug puts("**debug**")

#define LL long long

#define PB push_back

#define MP make_pair

using namespace std;

const int N = 100100;

const int INF = 1e9 + 7;

struct Node

{

    int s, b, id;

    bool operator < (const Node &rhs) const

    {

        return s < rhs.s || (s == rhs.s && b > rhs.b);

    }

}p[N];

int g[N];

int d[N];

int main()

{

    int s, b, t, n, ans;

    scanf("%d", &t);

    while(t --)

    {

        scanf("%d", &n);

        for(int i = 0; i < n; i ++)

        {

            scanf("%d%d", &s, &b);

            p[i].s = s, p[i].b = b, p[i].id = i + 1;

        }

        sort(p, p + n);ans = 0;

        for(int i = 1; i <= n; i ++) g[i] = INF;

        for(int i = 0; i < n; i ++)

        {

            int k = lower_bound(g+1, g+n+1, p[i].b) - g;

            g[k] = p[i].b;

            d[i] = k;

            ans = max(ans, k);

        }

        printf("%d\n", ans);

        int pt = -1;

        for(int i = n - 1; i >= 0; i --)

        {

            if(p[i].s != pt && d[i] == ans)

            {

                printf("%d", p[i].id);

                if(ans) putchar(' ');

                ans --;pt = p[i].s;

            }

            if(!ans) break;

        }puts("");

        if(t) puts("");

    }

}

巴特西

ZOJ 2319 Beautiful People

最新文章

热门文章