首页 > ACM题库 > HDU-杭电 > hdu 2691 2-Dimensional Rubik’s Cube-线段树-[解题报告]C++
2014
02-13

hdu 2691 2-Dimensional Rubik’s Cube-线段树-[解题报告]C++

2-Dimensional Rubik’s Cube

问题描述 :

Alex loves Rubik’s Cube. The 3-dimensional cubes are so difficult that Alex can only challenge the 2D ones, which have
six colors: W, Y, R, O, G, B.

Alex names the six faces as U(upper), D(bottom), L(left), R(right), F(front), B(back). The expanded cube will appear like
this:

Alex is able to rotate any face 90 degrees in clockwise or counter-clockwise in a second. U, D, L, R, F, B are used for rotating the
corresponding face in clockwise, while U’, D’, L’, R’, F’, B’ are for counter-clockwise.

Now Alex got a Cube, he wants to know the minimum number of steps required for making one state to the other.

输入:

The input consists of multiple test cases. The first line of input contains an integer T, which is the number of
test cases.

Each test case is on 12 lines. The first 6 lines indicate the initial state, while the next 6 lines indicate the destination state,
both according to the form of the sample input.

[Technical Specification]
T is an integer, and T <= 10.
You can assume that it is always possible to complete the task.

输出:

The input consists of multiple test cases. The first line of input contains an integer T, which is the number of
test cases.

Each test case is on 12 lines. The first 6 lines indicate the initial state, while the next 6 lines indicate the destination state,
both according to the form of the sample input.

[Technical Specification]
T is an integer, and T <= 10.
You can assume that it is always possible to complete the task.

样例输入:

1 
    G W 
    Y G 
W G O Y R B O R 
Y B R W G B O B 
    W O 
    R Y 
    B B 
    B B 
O O W W R R Y Y 
O O W W R R Y Y 
    G G 
    G G 

样例输出:

10 

#include <iostream>
#include <algorithm>
#include <map>
#define N 100010
#define M 50010
using namespace std;
struct data
{
    int r,l,v,d,b;                                  //r、l分别为区间的左右端点,v为查询的高度,d为输入时的顺序,b为答案
    void input(int k)
    {
        d=k;
        scanf("%d %d %d",&r,&l,&v);
    }
}p[M];
int a[N];
map<int,int>g;
bool cmp1(const data a,const data b)  //按照区间左端点排序的比较函数
{
    return a.r<b.r;
}
bool cmp2(const data a,const data b) //按照输入顺序排序的比较函数
{
    return a.d<b.d;
}
int main()
{
    int n,m,i,j,k;
    while(scanf("%d %d",&n,&m)==2)
    {
        for(i=0;i<n;i++)
            scanf("%d",a+i+1);
        for(i=0;i<m;i++)
            p[i].input(i);
        sort(p,p+m,cmp1);                       //按照区间左端点排序
        g.clear();
        map<int,int>::iterator pos;
        j=1;
        k=1;
        for(i=0;i<m;i++)
        {
            for(;j<=p[i].l&&j<=n;j++)         //将未入map的钉子加入,由于upper_bound返回的是大于等于,所以改成复数加入
                g[-a[j]]=j;
            while(1)
            {
                pos=g.lower_bound(-p[i].v);  //查询
                if(pos==g.end())                 //如果没有查到,则木板掉落到地上,输出0
                {
                    p[i].b=0;
                    break;
                }
                if(pos->second<p[i].r)      //如果查到的钉子位置在此区间以前,则删除掉
                    g.erase(pos);
                else
                {
                    p[i].b=-pos->first;     //此为查到了区间内第一个小于等于v的钉子
                    break;
                }
            }
        }
        sort(p,p+m,cmp2);         //按照输入顺序排序
        for(i=0;i<m;i++)
        {
            printf("%d\n",p[i].b);
        }
    }
    return 0;
}

解题转自:http://blog.csdn.net/a578559967/article/details/7255161


  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。