线段树/树状数组 POJ 2182 Lost Cows

题意：n头牛，1~n的id给它们乱序编号，已知每头牛前面有多少头牛的编号是比它小的，求原来乱序的编号

分析：从后往前考虑，最后一头牛a[i] = 0，那么它的编号为第a[i] + 1编号：为1，倒数第二头牛的编号为除去最后一头牛的编号后的第a[i-1] + 1编号：为3，其他的类推，所以可以维护之前已经选掉的编号，求第k大的数字，sum[rt] 表示该区间已经被选掉的点的个数。另外树状数组也可以做，只不过用二分优化查找第k大的位置。

收获：逆向思维，求动态第K大

代码(线段树)：

/************************************************

* Author        :Running_Time

* Created Time  :2015/9/9 星期三 17:01:08

* File Name     :P.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 8e3 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

struct ST   {

    int sum[N<<2];

    void build(int l, int r, int rt)    {

        sum[rt] = 0;

        if (l == r) return ;

        int mid = (l + r) >> 1;

        build (lson);

        build (rson);

    }

    int query(int p, int l, int r, int rt)  {

        sum[rt]++;

        if (l == r) return l;

        int mid = (l + r) >> 1;

        int tmp = mid - l + 1 - sum[rt<<1];

        if (tmp >= p)    return query (p, lson);

        else    {

            return query (p - tmp, rson);

        }

    }

}st;

int a[N], ans[N];

int main(void)    {

    int n;

    while (scanf ("%d", &n) == 1)   {

        a[1] = 0;

        for (int i=2; i<=n; ++i) {

            scanf ("%d", &a[i]);

        }

        st.build (1, n, 1);

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

            ans[i] = st.query (a[i] + 1, 1, n, 1);

        }

        for (int i=1; i<=n; ++i)    {

            printf ("%d\n", ans[i]);

        }

    }

    return 0;

}

代码(树状数组)：

/************************************************

* Author        :Running_Time

* Created Time  :2015/9/9 星期三 18:19:28

* File Name     :P_BIT.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 8e3 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

int n;

struct BIT  {

    int c[N];

    void init(void) {

        memset (c, 0, sizeof (c));

    }

    void updata(int i, int x)  {

        while (i <= n)   {

            c[i] += x;  i += i & (-i);

        }

    }

    int query(int i)    {

        int ret = 0;

        while (i)   {

            ret += c[i];    i -= i & (-i);

        }

        return ret;

    }

    int bsearch(int l, int r, int k)    {

        while (l <= r)  {

            int mid = (l + r) >> 1;

            if (mid - query (mid) >= k) r = mid - 1;

            else    l = mid + 1;

        }

        return l;

    }

}bit;

int a[N], ans[N];

int main(void)    {

    while (scanf ("%d", &n) == 1)   {

        a[1] = 0;

        for (int i=2; i<=n; ++i)    scanf ("%d", &a[i]);

        bit.init ();

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

            ans[i] = bit.bsearch (1, n, a[i] + 1);

            bit.updata (ans[i], 1);

        }

        for (int i=1; i<=n; ++i)    {

            printf ("%d\n", ans[i]);

        }

    }

    return 0;

}

巴特西

线段树/树状数组 POJ 2182 Lost Cows

最新文章

热门文章