这个题目我的思路很简单，就是读入一个数据，判断是否小于s1的顶元素，如果是则讲数据压入s1，否则该数据是否小于s2的顶元素，如果是则将它压入栈s2。然后再判断s1的顶是否等于当前需要输出的值（就是安顺序来是不是对的），如果是就输出b。再同样判断s2，如果是就输出d。
很可惜，只有30分，代码如下：
#include <stdio.h>
int num[1000];
int s1[1000], s2[1000];
int t1, t2;
char ans[2000];
int len;
void add(char ch)
{
ans[len++] = ch;
}
int main(void)
{
int n;
int i, j, r, t;
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d", &num[i]);
}
s1[0] = s2[0] = 10000;
for(i = 1, j = 0; i <= n;){
r = j;
if(s1[t1] > num[j] && j < n){
s1[++t1] = num[j++];
add(‘a’);
}else if(s2[t2] > num[j] && j < n){
s2[++t2] = num[j++];
add(‘c’);
}
t = i;
if(s1[t1] == i){
t1–;
add(‘b’);
i++;
}
if(s2[t2] == i){
t2–;
i++;
add(‘d’);
}
if(t == i && r == j){
printf("0\n");
return 0;
}
}
for(i = 0; i < 2 n; i++){
if(i != 0){
printf(" ");
}
printf("%c", ans[i]);
}
printf("\n");
return 0;
}
继续学习中。。
额, 照着网上一个人抄的(当然是在理解的前提下, 再自己徒手打出来的.), 竟然没有AC, 然后试了试他自己的代码, 也没AC
思路是这样的, 对于这样的数据i < j < k 且 num[k] < num[i] < num[j] 的情况下，i和j一定不能在同一个栈中，不然就是无解的情况，你想想啊，如果小的先入栈，大的又入栈，这能有解码？所以这里使用了二分图染色的算法，具体的解释看这位大牛和另一位的Blog:
http://www.byvoid.com/blog/noip2008-twostack/
下面那个是90分的代码，上面那个是100分的代码。
先贴代码吧:
#include <stdio.h>
#define minnum(a, b) ((a)<(b)?(a):(b))
int num[1000];
int min[1000];
int map[1000][1000];
int count[1000];
int color[1000];
void add(int i, int j)
{
map[i][count[i]++] = j;
}
int fill(int i, int c)
{
int j, t;
color[i] = c;
for(j = 0; j < count[i]; j++){
t = map[i][j];
if(color[t] == –1 && !fill(t, c ^ 1)){
return 0;
}else if(color[t] == c){
return 0;
}
}
return 1;
}
int s1[1000], s2[1000];
int t1, t2;
int main(void)
{
int n;
int i, j;
char tmp;
memset(min, 0x7F, sizeof(min));
memset(color, 0xFF, sizeof(color));
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d", &num[i]);
}
for(i = n – 1; i >= 0; i–){
min[i] = minnum(min[i + 1], num[i]);
}
for(i = 0; i < n; i++){
for(j = i + 1; j < n; j++){
if(num[i] < num[j] && num[i] > min[j]){
add(i, j);
add(j, i);
}
}
}
for(i = 0; i < n; i++){
if(color[i] == –1){
if(!fill(i, 0)){
printf("0\n");
return 0;
}
}
}
j = 0;
tmp = "";
for(i = 1; i <= n; ){
if(s1[t1] == i){
printf("%sb", tmp);
t1–, i++;
continue;
}
if(s2[t2] == i && (j >= n || color[j])){
printf("%sd", tmp);
t2–, i++;
continue;
}
if(!color[j]){
printf("%sa", tmp);
tmp = " ";
s1[++t1] = num[j++];
}else{
printf("%sc", tmp);
tmp = " ";
s2[++t2] = num[j++];
}
}
printf("\n");
// getch();
return 0;
}
#include <stdio.h>
#define minnum(a, b) ((a)<(b)?(a):(b))
int num[1000];
int min[1001];
int map[1000][1000];
int count[1000];
int color[1000];
void add(int i, int j)
{
map[i][count[i]++] = j;
}
int fill(int i, int c)
{
int j, t;
color[i] = c;
for(j = 0; j < count[i]; j++){
t = map[i][j];
if(color[t] == –1 && !fill(t, c ^ 1)){
return 0;
}else if(color[t] == c){
return 0;
}
}
return 1;
}
int s1[1000], s2[1000];
int t1, t2;
int main(void)
{
int n;
int i, j;
char *tmp;
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d", &num[i]);
}
min[n] = 10001;
for(i = n – 1; i >= 0; i–){
min[i] = minnum(min[i + 1], num[i]);
}
for(i = 0; i < n; i++){
for(j = i + 1; j < n; j++){
if(num[i] < num[j] && num[i] > min[j]){
add(i, j);
add(j, i);
}
}
}
for(i = 0; i < n; i++){
color[i] = –1;
}
for(i = 0; i < n; i++){
if(color[i] == –1){
if(!fill(i, 0)){
printf("0\n");
return 0;
}
}
}
j = 0;
tmp = "";
for(i = 1; i <= n; ){
if(s1[t1] == i){
printf("%sb", tmp);
t1–, i++;
continue;
}
if(s2[t2] == i && (j >= n || color[j])){
printf("%sd", tmp);
t2–, i++;
continue;
}
if(!color[j]){
printf("%sa", tmp);
tmp = " ";
s1[++t1] = num[j++];
}else{
printf("%sc", tmp);
tmp = " ";
s2[++t2] = num[j++];
}
}
printf("\n");
// getch();
return 0;
}