题解 UVA12657 【移动盒子 Boxes in a Line】
Countjoyyauldly · · 题解
前言
看大佬们的写法，我觉得我用stl好无耻方便
本蒟蒻可能写法有些菜，但是希望对迷茫的同学有些帮助
说实话uva太容易崩了
正文
明显这道题不能用数组纯肝，第一数据大，第二操作起来特别麻烦，于是我们选择使用链表。值得一提的是第四个操作直接提示了用stl里的list，因为其中有reverse操作，与其相符。
先上网址 list详解
我们就对题目进行模拟，具体思路如下：
题目： 你有n个盒子在桌子上的一条线上从左到右编号为1……n。你的任务是模拟四种操作
所以我们需要先建立链表以备后面的处理，这里我不知道有没有更好的方法来建立链表，我的方法是这样：
list<int>as;
for(int i=1;i<=n;i++)
as.insert(++as.begin(),1,i);
as.sort();先插入1到n这n个元素，然后进行sort排序（list刚好提供这样的函数）
建立链表搞定了，开始操作：
操作1：1 X Y 移动盒子编号X到盒子编号Y的左边（如果X已经在Y的左边了就忽略）
我们这里可以看作用指针指向y的位置，然后删掉x， 再在指针位置插入x即可
伪代码如下：
case 1:{
int a, b;
cin>> a>> b;
auto iter=begin(as);//定义一个指针
advance(iter,b-1);
as.remove(a);
as.insert(iter,1,a);
break;
}操作2：2 X Y 移动盒子编号X到盒子编号Y的右边（如果X已经在Y的右边了就忽略）
思路与操作1相同，伪代码如下：
case 2:{
int a, b;
cin>> a>> b;
auto iter=begin(as);
advance(iter,b);
as.remove(a);
as.insert(iter,1,a);
break;
}操作3：3 X Y 交换盒子编号X与盒子编号Y的位置
这里就是操作1的升级版，需要两个指针，分别指向x与y， 再删除x与y，再在指针位置插入y与x即可
伪代码如下：
case 3:{
int a, b;
cin>> a>> b;
auto iter1=begin(as);
auto iter2=begin(as);
advance(iter1,b);
as.remove(b);
advance(iter2,a+1);
as.remove(a);
as.insert(iter1,1,a);
as.insert(iter2,1,b);
break;
}操作4：4 将整条线反转
这个就简单了，直接reverse即可
case 4:
reverse(as.begin(),as.end());
break;具体操作就是这样，输出即可
代码如下
#include<bits/stdc++.h>
using namespace std;
int main()
{
//freopen("text\\in.txt","r",stdin);
//freopen("text\\out.txt","w",stdout);
int n,m,work,t=1;
int ans[100005];
int k=0;
unsigned long long ans2 = 0;
int sum=0;
memset(ans,0,sizeof(ans));
while(cin>>n>>m)
{
sum++;
list<int>as;
for(int i=1;i<=n;i++)
as.insert(++as.begin(),1,i);
as.sort();
while(m--){
int op;
cin>> op;
switch(op){
case 1:{
int a, b;
cin>> a>> b;
auto iter=begin(as);
advance(iter,b-1);
as.remove(a);
as.insert(iter,1,a);
break;
}
case 2:{
int a, b;
cin>> a>> b;
auto iter=begin(as);
advance(iter,b);
as.remove(a);
as.insert(iter,1,a);
break;
}
case 3:{
int a, b;
cin>> a>> b;
auto iter1=begin(as);
auto iter2=begin(as);
advance(iter1,b);
as.remove(b);
advance(iter2,a+1);
as.remove(a);
as.insert(iter1,1,a);
as.insert(iter2,1,b);
break;
}
case 4:
reverse(as.begin(),as.end());
break;
}
}
cout<<"Case "<<++k<<": ";
for(int i=1;i<=n;i++)
{
ans[i]=as.front();
as.pop_front();
}
for(int i=1;i<=n;i++)
{
if(i%2==0) continue;
else ans2+=ans[i];
}
cout<<ans2<<endl;
ans2=0;
as.erase(as.begin(),as.end());
}
return 0;
}
希望可以过，谢谢管理大大！