POJ 1785 treap 或 RMQ

[cpp]
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 55555
#define MAXM 5555
#define INF 100000007
using namespace std;
struct node
{
    int w, fa, lch, rch;
    char s[111];
    bool operator <(const node& a)const
    {
        return strcmp(s, a.s) <= 0;
    }
}p[MAXN];
int n;
void insert(int i)
{
    int j = i - 1;
    while(p[j].w < p[i].w) j = p[j].fa;
    p[i].lch = p[j].rch;
    p[j].rch = i;
    p[i].fa = j;
}
void solve(int rt)
{
    if(rt == 0) return;
    printf("(");
    solve(p[rt].lch);
    printf("%s/%d", p[rt].s, p[rt].w);
    solve(p[rt].rch);
    printf(")");
}
int main()
{
    char s[111], tmp[111];
    while(scanf("%d", &n) != EOF && n)
    {
        for(int i = 1; i <= n; i++)
        {
            scanf("%s", s);
            int j;
            for(j = 0; s[j]; j++)
                if(s[j] == '/') break;
                    else tmp[j] = s[j];
            tmp[j++] = '\0';
            int num = 0;
            while(s[j]) {num = num * 10 + s[j] - '0'; j++;}
            strcpy(p[i].s, tmp);
            p[i].w = num;
            p[i].lch = p[i].rch = 0;
            p[i].fa = 0;
        }
        sort(p + 1, p + n + 1);
        p[0].w = INF;
        p[0].lch = p[0].rch = p[0].fa = 0;
        for(int i = 1; i <= n; i++) insert(i);
        solve(p[0].rch);
        printf("\n");
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 55555
#define MAXM 5555
#define INF 100000007
using namespace std;
struct node
{
    int w, fa, lch, rch;
    char s[111];
    bool operator <(const node& a)const
    {
        return strcmp(s, a.s) <= 0;
    }
}p[MAXN];
int n;
void insert(int i)
{
    int j = i - 1;
    while(p[j].w < p[i].w) j = p[j].fa;
    p[i].lch = p[j].rch;
    p[j].rch = i;
    p[i].fa = j;
}
void solve(int rt)
{
    if(rt == 0) return;
    printf("(");
    solve(p[rt].lch);
    printf("%s/%d", p[rt].s, p[rt].w);
    solve(p[rt].rch);
    printf(")");
}
int main()
{
    char s[111], tmp[111];
    while(scanf("%d", &n) != EOF && n)
    {
        for(int i = 1; i <= n; i++)
        {
            scanf("%s", s);
            int j;
            for(j = 0; s[j]; j++)
                if(s[j] == '/') break;
                    else tmp[j] = s[j];
            tmp[j++] = '\0';
            int num = 0;
            while(s[j]) {num = num * 10 + s[j] - '0'; j++;}
            strcpy(p[i].s, tmp);
            p[i].w = num;
            p[i].lch = p[i].rch = 0;
            p[i].fa = 0;
        }
        sort(p + 1, p + n + 1);
        p[0].w = INF;
        p[0].lch = p[0].rch = p[0].fa = 0;
        for(int i = 1; i <= n; i++) insert(i);
        solve(p[0].rch);
        printf("\n");
    }
    return 0;
}

然后还可以使用RMQ来搞

还是首先要排序

每次递归处理一个区间，找出有最大第二关键字的那个做根。他左边的就是他的左子树，右边的是右子树

[cpp]
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define

补充：软件开发 , C++ ,