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

POJ 3667 Hotel [解题报告] Java

Hotel

问题描述 :

The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).

The cows and other visitors arrive in groups of size Di (1 ≤ Di ≤ N) and approach the front desk to check in. Each group i requests a set of Di contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+Di-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.

Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and Di which specify the vacating of rooms Xi ..Xi +Di-1 (1 ≤ XiN-Di+1). Some (or all) of those rooms might be empty before the checkout.

Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.

输入:

* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and Di (b) Three space-separated integers representing a check-out: 2, Xi, and Di

输出:

* Lines 1…..: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.

样例输入:

10 6
1 3
1 3
1 3
1 3
2 5 5
1 6

样例输出:

1
4
7
0
5

解题代码:

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 point
{
    int l,r,max,cov;
}
 public class Main{
  // static int  MAX = 50010;


   point p[];
   public Main(){
      p=new point[131070];
      for(int i=0;i< p.length;i++)
         p[i]=new point();
   }
  
  void push_up(int l,int r,int rt)
  {
    p[rt].l = p[rt<<1].l;
    p[rt].r = p[rt<<1|1].r;
    int mid = r+l>>1;
    if(p[rt].l==mid-l+1) p[rt].l+=p[rt<<1|1].l;
    if(p[rt].r==r-mid) p[rt].r+=p[rt<<1].r;
    p[rt].max =Math.max(Math.max(p[rt<<1].max,p[rt<<1|1].max),p[rt<<1].r+p[rt<<1|1].l);
 }

  void push_down(int l,int r,int rt)
  {
    if(p[rt].cov!=-1)
    {
        p[rt<<1].cov = p[rt<<1|1].cov = p[rt].cov;
        if(p[rt].cov==1)
        p[rt<<1].l = p[rt<<1|1].l = p[rt<<1].r = p[rt<<1|1].r = p[rt<<1].max = p[rt<<1|1].max = 0;
        else
        {
            int mid = r+l>>1;
            p[rt<<1].l = p[rt<<1].r = p[rt<<1].max = mid-l+1;
            p[rt<<1|1].l = p[rt<<1|1].r = p[rt<<1|1].max = r-mid;
        }
        p[rt].cov = -1;
    }
 }

 void build(int l,int r,int rt){
    p[rt].l = p[rt].r = p[rt].max = r-l+1;
    p[rt].cov = -1;
    if(l==r)
    {
        return;
    }
    int mid = r+l>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
 }

 //a==1,填满[L,R],a=0清空区间[L,R]
 void update(int a,int L,int R,int l,int r,int rt)
 {
    if(L<=l&&R>=r)
    {
        if(a==1)
          p[rt].l = p[rt].r = p[rt].max = 0;
        else
          p[rt].l = p[rt].r = p[rt].max = r-l+1;
        p[rt].cov = a;
        return;
    }
    int mid = r+l>>1;
    push_down(l,r,rt);
    if(L<=mid) update(a,L,R,l,mid,rt<<1);
    if(R>mid) update(a,L,R,mid+1,r,rt<<1|1);
    push_up(l,r,rt);
 }
 
  int query(int a,int l,int r,int rt)
  {
    if(l==r)
    {
        return l;
    }
    int mid = r+l>>1;
    push_down(l,r,rt);
    if(p[rt<<1].max>=a) return query(a,l,mid,rt<<1);
    if(p[rt<<1].r+p[rt<<1|1].l>=a) return mid-p[rt<<1].r+1;
    return query(a,mid+1,r,rt<<1|1);
 }

  public int getMax(){
    return p[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));   
     

    int n,m,k,x,y;
    while(st.nextToken() != StreamTokenizer.TT_EOF)
    {
        
         n= (int) st.nval;
          st.nextToken();   
         m= (int) st.nval;
         Main ma=new Main();
        
        ma.build(1,n,1);
        while(m-->0)
        {
            st.nextToken();   
            k=(int) st.nval;
            if(k==1)
            {
                 st.nextToken();   
                x= (int) st.nval;
                if(ma.getMax()< x) System.out.println("0");
                else
                {
                    int tmp =ma.query(x,1,n,1);
                    System.out.printf("%d\n",tmp);
                    ma.update(1,tmp,tmp+x-1,1,n,1);
                }
            }
            else
            {
                 st.nextToken();   
                x=(int) st.nval;
                 st.nextToken();
                y=(int) st.nval;
                ma.update(0,x,x+y-1,1,n,1);
            }
        }
       out.flush();   
    }
   }
}

  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  3. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了

  4. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。