首页 > 专题系列 > Java解POJ > POJ 1823 Hotel [解题报告] Java
2013
11-10

POJ 1823 Hotel [解题报告] Java

Hotel

问题描述 :

The “Informatics” hotel is one of the most luxurious hotels from Galaciuc. A lot of tourists arrive or leave this hotel in one year. So it is pretty difficult to keep the evidence of the occupied rooms. But this year the owner of the hotel decided to do some changes. That’s why he engaged you to write an efficient program that should respond to all his needs.

Write a program that should efficiently respond to these 3 types of instructions:

type 1: the arrival of a new group of tourists

A group of M tourists wants to occupy M free consecutive rooms. The program will receive the number i which represents the start room of the sequence of the rooms that the group wants to occupy and the number M representing the number of members of the group. It is guaranteed that all the rooms i,i+1,..,i+M-1 are free at that moment.

type 2: the departure of a group of tourists

The tourists leave in groups (not necessarilly those groups in which they came). A group with M members leaves M occupied and consecutive rooms. The program will receive the number i representing the start room of the sequence of the released rooms and the number M representing the number of members of the group. It is guaranteed that all the rooms i,i+1,..,i+M-1 are occupied.

type 3: the owner’s question

The owner of the hotel may ask from time to time which is the maximal length of a sequence of free consecutive rooms. He needs this number to know which is the maximal number of tourists that could arrive to the hotel. You can assume that each room may be occupied by no more than one tourist.

输入:

On the first line of input, there will be the numbers N (3 <= N <= 16 000) representing the number of the rooms and P (3 <= P <= 200 000) representing the number of the instructions.

The next P lines will contain the number c representing the type of the instruction:

  • if c is 1 then it will be followed (on the same line) by 2 other numbers, i and M, representing the number of the first room distributed to the group and the number of the members
  • if c is 2 then it will be followed (on the same line) by 2 other numbers, i and M, representing the number of the first room that will be released and the number of the members of the group that is leaving
  • if c is 3 then it will not be followed by any number on that line, but the program should output in the output file the maximal length of a sequence of free and consecutive rooms

输出:

In the output you will print for each instruction of type 3, on separated lines, the maximal length of a sequence of free and consecutive rooms. Before the first instruction all the rooms are free.

样例输入:

12 10
3
1 2 3
1 9 4
3
2 2 1
3
2 9 2
3
2 3 2
3 

样例输出:

12
4
4
6
10

解题代码:

import java.io.StreamTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;

  class Tree{ 
        int ll,rr,mid; 
        int max,cl,cr;
        //max表示结点管理的区间最大的连续子区间有多大,cl表示区间的最左边有多少连续的区间,
        //cr表示区间的右边有多少连续的子区间 
        int occ;//occ==0表示空,occ=1表示全部入住,occ=-1表示有空有住 
    }
   public class Main{
     Tree tree[]; 
    public Main(){
       tree=new Tree[32766];
       for(int i=0;i< tree.length;i++){
            tree[i]=new Tree();
       }
    }
    

    void build(int id,int ll,int rr){ 
        tree[id].ll=ll;tree[id].rr=rr;tree[id].mid=(ll+rr)>>1; 
        //刚开始建树,都是空的,所以可以这样写 
        tree[id].max=tree[id].cl=tree[id].cr=rr-ll+1; 
        tree[id].occ=0; 
        if(ll==rr)return; 
        build(id< < 1,ll,tree[id].mid); 
        build(id< < 1|1,tree[id].mid+1,rr); 
    } 

    void push_down(int id,int sign){//sign=1表示入住,sign=0表示退房 
        tree[id].occ=-1;//表示有空有住 
        tree[id<<1].occ=tree[id<<1|1].occ=sign;//表示全空或者全住 
        if(sign==1){ 
            tree[id<<1].cl=tree[id<<1|1].cl=tree[id<<1].cr=tree[id<<1|1].cr=0; 
            tree[id<<1].max=tree[id<<1|1].max=0; 
        }else{ 
            int len=tree[id<<1].rr-tree[id<<1].ll+1; 
            tree[id<<1].cl=tree[id<<1].cr=len; 
            tree[id<<1].max=len; 
            len=tree[id<<1|1].cr=tree[id<<1|1].rr-tree[id<<1|1].ll+1; 
            tree[id<<1|1].cl=len; 
            tree[id<<1|1].max=len; 
        } 
    } 

    //更新区间 
    void update(int id ,int ll,int rr,int sign){//sign=1入住,sign=0表示退房 
        if(tree[id].ll==ll&&tree[id].rr==rr){//找到区间 
            tree[id].occ=sign; 
            int len=tree[id].rr-tree[id].ll+1; 
            if(sign==1) len=0; 
            tree[id].cl=tree[id].cr=len; 
            tree[id].max=len; 
            return; 
        } 
        if(tree[id].occ==1)
            push_down(id,1);//执行到这行代码意味着 tree[id]的子区间要更改了,所以需要执行一次push_down 
        if(tree[id].occ==0)
          push_down(id,0);
        if(rr<=tree[id].mid){ 
            update(id*2,ll,rr,sign); 
        }else if(ll>tree[id].mid){ 
            update(id*2+1,ll,rr,sign); 
        }else{ 
            update(id*2,ll,tree[id].mid,sign);
            update(id*2+1,tree[id].mid+1,rr,sign); 
        } 
        //子区间更新了,必须更新父区间
        //需要修改的就只有3个值:max,cl,cr 分别代表最长连续个数为多少,最左边有多少个空闲,最右边有多少个空闲 
        if(tree[id].occ==-1){//表示有空有住 
            if(tree[id<<1].occ==0){ 
                tree[id].cl=tree[id*2].cl+tree[id<<1|1].cl; 
            }else{ 
                tree[id].cl=tree[id<<1].cl; 
            } 
            if(tree[id<<1|1].occ==0){ 
                tree[id].cr=tree[id*2].cr+tree[id<<1|1].cr; 
            }else{ 
                tree[id].cr=tree[id<<1|1].cr; 
            } 
            //求tree[id].max 
            int len=tree[id<<1].cr+tree[id<<1|1].cl; 
            tree[id].max=Math.max(len,Math.max(tree[id<<1].max,tree[id<<1|1].max)); 
        }else{//表示全空或者全住 
            int len; 
            
            if(sign==1)
                len=0;
            else
                len=tree[id].rr-tree[id].ll+1; 
            tree[id].max=tree[id].cl=tree[id].cr=len; 
        } 
        if(tree[id*2].occ==tree[id*2+1].occ) 
            tree[id].occ=tree[id*2].occ; 
    } 

     int getMax(){
       return tree[1].max;
     }

public static void main(String[] args) throws IOException{

  StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  //PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

          st.nextToken();

         int n= (int) st.nval;
          
          st.nextToken();
         int p=(int) st.nval;
     //  long start=System.currentTimeMillis();//获取开始时间
         Main ma=new Main();
        int sign; 
        int ll,rr; 
        ma.build(1,1,n); 
        for(int i=0;i< p;i++){ 
              st.nextToken();
            sign=(int) st.nval;
            if(sign==3){ 
               System.out.printf("%d\n",ma.getMax()); 
            }else{ 
                st.nextToken();
                ll=(int) st.nval;
                st.nextToken();

                rr=(int) st.nval;
                rr=ll+rr-1; 
                if(sign==2)
                  sign=0;
                ma.update(1,ll,rr,sign); 
            } 
        } 
      // out.flush();
      }
  }

  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience