ECNU_1082//火车调度,在每个数后,小于它的数必须以逆序排列。此题的另一解法是用栈模拟。
#include<iostream>
using namespace std;
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int T,n,i,j,temp,cur;
bool flag;
int s[10];
char c;
scanf("%d",&T);
while(T--)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d",&n);
flag = false;
getchar();
for(i = 0; i < n; i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
c = getchar();
s[i] = c - '0';
}
for(i = 0 ; i < (n-2); i ++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cur = s[i];
for(j = i+1; j < n; j++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(s[j] < s[i])
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(s[j] < cur)
cur = s[j];
else
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
flag = true;
break;
}
}
}
if(flag)
break;
}
if(flag)
puts("no");
else
puts("yes");
}
}//HDU_1022,用栈模拟,pop,push 2个操作轮流看是否可以进行,都不行则说明不可行。因为要输出过程。否则可以按Order1中数字出现的次序重新定义Order2中的数字,然后采用ECNU_1082的方法,构成第2种解法。
#include<iostream>
using namespace std;
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int n,i,j,ohead,stail,in_our_cur;
int o1[10];
int o2[10];
int s[10];
int in_our[20];
bool flag;
while(scanf("%d",&n)!=EOF)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
getchar();
for(i = 0; i < n; i++)
o1[i] = getchar()-'0';
getchar();
for(i = 0; i < n; i++)
o2[i] = getchar()-'0';
flag = false;
ohead = 0;
stail = -1;
in_our_cur = 0;
for(i = 0; i < n; i++)//o2
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(stail >= 0 && s[stail] == o2[i])
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
in_our[in_our_cur++] = 1;//out
stail--;
continue;
}
while(o1[ohead] != o2[i] && ohead < n)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
s[++stail] = o1[ohead];
ohead++;
in_our[in_our_cur++] = 0;//in
}
if(ohead == n)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("No.\nFINISH\n");
flag = true;
break;
}
in_our[in_our_cur++] = 0;//in
in_our[in_our_cur++] = 1;//out
ohead++;
![](/Images/OutliningIndicators/InBlock.gif)
}
if(!flag)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("Yes.\n");
for(i = 0; i < in_our_cur; i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(in_our[i] == 0)
printf("in\n");
else
printf("out\n");
}
printf("FINISH\n");
}
![](/Images/OutliningIndicators/InBlock.gif)
}
}