[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 MAXN 55555
#define MAXM 5555
#define INF 100000007
using namespace std;
struct node
{
int w;
char s[111];
bool operator <(const node& a)const
{
return strcmp(s, a.s) <= 0;
}
}p[MAXN];
int mi[MAXN][17], mx[MAXN][17];
int n;
void rmqinit()
{
for(int i = 1; i <= n; i++) mi[i][0] = mx[i][0] = i;
int m = (int)(log(n * 1.0) / log(2.0));
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
{
mx[j][i] = mx[j][i - 1];
mi[j][i] = mi[j][i - 1];
int k = j + (1 << (i - 1));
if(k <= n)
{
if(p[mx[j][i]].w < p[mx[k][i - 1]].w) mx[j][i] = mx[k][i - 1];
if(p[mi[j][i]].w > p[mi[k][i - 1]].w) mi[j][i] = mi[k][i - 1];
}
}
}
int rmqmax(int l, int r)
{
int m = (int)(log((r - l + 1) * 1.0) / log(2.0));
if(p[mx[l][m]].w < p[mx[r - (1 << m) + 1][m]].w) return mx[r - (1 << m) + 1][m];
else return mx[l][m];
}
void solve(int s, int t)
{
if(s > t) return;
int pos = rmqmax(s, t);
printf("(");
solve(s, pos - 1);
printf("%s/%d", p[pos].s, p[pos].w);
solve(pos + 1, t);
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;
}
sort(p + 1, p + n + 1);
rmqinit();
solve(1, n);
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;
char s[111];
bool operator <(const node& a)const
{
return strcmp(s, a.s) <= 0;
}
}p[MAXN];
int mi[MAXN][17], mx[MAXN][17];
int n;
void rmqinit()
{
for(int i = 1; i <= n; i++) mi[i][0] = mx[i][0] = i;
int m = (int)(log(n * 1.0) / log(2.0));
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
{
mx[j][i] = mx[j][i - 1];
mi[j][i] = mi[j][i - 1];
int k = j + (1 << (i - 1));
if(k <= n)
{
if(p[mx[j][i]].w < p[mx[k][i - 1]].w) mx[j][i] = mx[k][i - 1];
if(p[mi[j][i]].w > p[mi[k][i - 1]].w) mi[j][i] = mi[k][i - 1];
}
}
}
int rmqmax(int l, int r)
{
int m = (int)(log((r - l + 1) * 1.0) / log(2.0));
if(p[mx[l][m]].w < p[mx[r - (1 << m) + 1][m]].w) return mx[r - (1 << m) + 1][m];
else return mx[l][m];
}
void solve(int s, int t)
{
if(s > t) return;
int pos = rmqmax(s, t);
printf("(");
solve(s, pos - 1);
printf("%s/%d", p[pos].s, p[pos].w);
solve(pos + 1, t);
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;
}
sort(p + 1, p + n + 1);
rmqinit();
solve(1, n);
printf("\n");
}
return 0;
}
