写个stl程序

明天就要acm课考试了,可是一学期几乎没去上过课(感觉有点对不住lcy老师啊。、、),肿么办。。没办法,只能临时抱抱佛脚,于是拿出了尘封已久的《算法竞赛入门经典》,话说当初刚接触acm的时候真心挺佩服刘汝佳的,大神啊,大二是就是世界第四了。可一年多过去后发现自己对这个没多少兴趣了。。

闲话不多说,切入正题,翻书的时候看到这样一道小题:

移动小球

你有一些小球,从左到右依次编号为1,2,3,……,n。指令A x y表示把小球x移动到小球y左边,B x y表示把小球x移动到小球y右边。指令保证合法(x不等于y)。输入小球个数n和指令条数m及m条指令,从左至右输出最后的序列。n可高达500000,m可高达100000.

样例输入:

6 2

A 1 4

B 3 5

样例输出:

2 1 4 5 3 6

 

这道题时间规模很大,因此书上采用数组模拟链表的方式实现。详见书。。

这里给出我的一个解法,用stl的list容器。

代码如下:

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
int main()
{
int n,m,x,y;
char type[3];
list<int> ball;
list<int>::iterator it;
while(scanf(“%d%d”,&n,&m)!=EOF)
{
for(int i=1;i<=n+1;i++)
ball.push_back(i);
for(int j=1;j<=m;j++)
{
scanf(“%s%d%d”,type,&x,&y);
if(type[0]==’A')
{
it=find(ball.begin(),ball.end(),y);
ball.remove(x);
ball.insert(it,x);
}
else
{
it=find(ball.begin(),ball.end(),y);
ball.remove(x);
ball.insert(++it,x);
}
}
ball.pop_back();
for(it=ball.begin();it!=ball.end();it++)
{
cout<<*it<<’ ‘;
}
cout<<endl;
ball.clear();
}
return 0;
}

这里有一点值得注意,因为list的迭代器不能实现+1等随机遍历(list实质是链表),所以只好用++操作替代,因而可能造成迭代器越界(find()返回ball.end()时)。所以这里我多创建一个元素,在输出前删除。由于使用while(scanf()!=EOF),所以每组数据结束后都要清空ball。

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>