首页 > 专题系列 > Java解POJ > POJ 3476 A Game with Colored Balls [解题报告] Java
2013
11-12

POJ 3476 A Game with Colored Balls [解题报告] Java

A Game with Colored Balls

问题描述 :

Given a chain of N (1 ≤ N ≤ 106) balls colored either red (‘R’), green (‘G’) or blue (‘B’) and numbered sequentially 1 through N from left to right, a game proceeds as follows:

  1. Pick the leftmost segment containing the largest number of consecutive balls of the same color.
  2. If the segment contains only one ball, the game ends; otherwise dislodge it from the chain. If the remaining balls are broken into two chains, join them maintaining their order.
  3. Report the color and numbers of the removed balls.
  4. Go back to step 1 if any balls remain.

Write a program to simulate the process of a game.

输入:

The input contains only a string of ‘R’s, ‘G’s and ‘B’s representing the balls in the chain from left to right.

输出:

For each segment dislodged, output whatever is reported following the sample output’s example.

样例输入:

GRRBBBRRGB

样例输出:

B 4 5 6
R 2 3 7 8
G 1 9

解题代码:

//* @author: Yeming Hu"[email protected]"
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
	BallSeq head, tail;
	BinaryHeap pq = new BinaryHeap();
	String s = sc.next();
	char previousChar = s.charAt(0);
        Ball ball = new Ball(0+1);
	BallSeq seq = new BallSeq(previousChar,0+1);
        head=seq;
        tail = seq;
	seq.firstBall = ball;
        seq.lastBall = ball;
	seq.number++;
	for(int i = 1; i < s.length(); i++)
	{
	    char currentChar = s.charAt(i);
	    if(currentChar==previousChar)
	    {
		ball = new Ball(i+1);
                seq.lastBall.nextBall = ball;
                //ball.previousBall = seq.lastBall;
                seq.lastBall = ball;
                seq.number++;
	    }else
	    {
		previousChar = currentChar;
                pq.offer(seq);
		seq = new BallSeq(previousChar,i+1);
                tail.nextBallSeq = seq;
                seq.previousBallSeq = tail;
                tail = seq;
		ball = new Ball(i+1);
                seq.firstBall = ball;
                seq.lastBall = ball;
		seq.number++;
	    }
	}
        pq.offer(seq);
	while(true)
	{
	    int size = pq.size();
	    if(size==0)
	    {
	        break;
	    }
	    seq = pq.poll();
	    if(seq.number==1)
	    {
	        break;
	    }
	    System.out.print(seq.color);
            ball = seq.firstBall;
	    for(int i = 0; i < seq.number; i++)
	    {
	        System.out.print(" "+ball.position);
                ball = ball.nextBall;
	    }
	    System.out.println();
	    if(seq == head)
            {
                head = seq.nextBallSeq;
                if(head != null)
                {
                    head.previousBallSeq = null;
                }
            }else if(seq == tail)
            {
                tail = seq.previousBallSeq;
                if(tail !=null )
                {
                    tail.nextBallSeq = null;
                }
            }else
            {
                BallSeq p = seq.previousBallSeq;
                BallSeq n = seq.nextBallSeq;
                if(p.color == n.color)
                {
                    pq.remove(p);
                    pq.remove(n);
                    p.number += n.number;
                    p.lastBall.nextBall = n.firstBall;
                    //n.firstBall.previousBall = p.lastBall;
                    p.lastBall = n.lastBall;
                    p.nextBallSeq = n.nextBallSeq;
                    if(n != tail)
                    {
                        n.nextBallSeq.previousBallSeq = p;
                    }else
                    {
                        tail =p;
                    }
                    pq.offer(p);
                }else
                {
                    p.nextBallSeq = n;
                    n.previousBallSeq = p;
                }
            }
	}
    }   
}

class BallSeq implements Comparable< BallSeq>
{
    public char color;
    public int number;
    public int start;
    public int position;
    Ball firstBall;
    Ball lastBall;
    BallSeq previousBallSeq;
    BallSeq nextBallSeq;
    public BallSeq(char color, int start)
    {
        this.color = color;
	this.start = start;
	this.number = 0;
        position = 0;
        firstBall = null;
        lastBall = null;
        previousBallSeq = null;
        nextBallSeq = null;
    }
    public int compareTo(BallSeq bs)
    {
        if(this.number == bs.number)
	{
	    if(this.start == bs.start)
	    {
	        return 0;
	    }else if(this.start < bs.start)
	    {
	        return -1;
	    }else
	    {
	        return 1;
	    }
	}else if(this.number < bs.number)
	{
	    return 1;
	}else
	{
	    return -1;
	}
    }
}

class Ball
{
    //Ball previousBall;
    Ball nextBall;
    int position;//position in the sequence
    public Ball(int position)
    {
        this.position = position;
        //previousBall = null;
        nextBall = null;
    }
}
class BinaryHeap
{
    public static final int max = 1000000;
    int count;
    BallSeq[] segments;
    public BinaryHeap()
    {
        count = 0;
        segments = new BallSeq[max];
    }
    public void offer(BallSeq seq)
    {
        if(count == max - 1)
        {
            throw new RuntimeException("Full Heap");
        }
        count++;
        int i = count;
        while(i > 1 && segments[i/2].compareTo(seq) == 1)
        {
            segments[i] = segments[i/2];
            segments[i].position = i;
            i = i/2;
        }
        segments[i] = seq;
        segments[i].position = i;
    }
    public void remove(BallSeq seq)
    {
        int i = seq.position;
        while(i > 1)
        {
            segments[i] = segments[i/2];
            segments[i].position = i;
            i = i/2;
        }
        segments[i] = seq;
        segments[i].position = i;
        poll();
    }
    public BallSeq poll()
    {
        if(count == 0)
        {
            throw new RuntimeException("Empty Heap");
        }
        BallSeq result = segments[1];
        BallSeq last = segments[count];
        count--;
        int i =1;
        while(2*i <= count)
        {
            int child = 2*i;
            if(child + 1 <= count && segments[child].compareTo(segments[child+1]) == 1)
            {
                child += 1;
            }
            if(last.compareTo(segments[child]) == -1)
            {
                break;
            }
            segments[i] = segments[child];
            segments[i].position = i;
            i = child;
        }
        segments[i] = last;
        segments[i].position = i;
        return result;
    }
    public int size()
    {
        return count;
    }
    public int capacity()
    {
        return max;
    }
}

  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?