考生位置调度

题目描述

假设有一个考场，考场有一排共 N 个座位，索引分别是 [0..N-1]，考生会陆续进入考场考试，并且可能在任何时候离开考场。

其他解法：连接

---

using System;
class ExamRoom
{
    struct Line
    {
        public int distance;
        public int startIndex;
        public int endIndex;
        public int subDis;
        public Line(int a,int b,int c,int d)
        {
            distance = a;
            subDis = b;
            startIndex = c;
            endIndex = d;
        }
    }

    int[] seats;

    public ExamRoom(int N)
    {
        seats = new int[N];
        for(int i=0; i<N; i++)
        {
            seats[i]=0;
        }
    }

    public int Seat()
    {
        Line maxLine = new Line(0, -1, 0 ,0);
        int start = 0;
        for(int end=0; end<seats.Length; end++)
        {
            if(seats[end]==1 || end==seats.Length-1)
            {
                int curDis = end - start;
                if(seats[start]==1 && seats[end]==1)
                    curDis--;
                if(curDis > maxLine.distance && (end-start)/2>maxLine.subDis)
                {
                    maxLine.distance = curDis;
                    maxLine.startIndex = start;
                    maxLine.endIndex = end;
                    maxLine.subDis = (end-start)/2;
                }
                start = end;
            }
        }

        if(maxLine.distance > 0)
        {
            if(seats[maxLine.startIndex] == 0 && seats[maxLine.endIndex]==0)
            {
                seats[maxLine.startIndex] =1;
                return maxLine.startIndex;
            }
            else if(seats[maxLine.startIndex] == 0)
            {
                seats[maxLine.startIndex] = 1;
                return maxLine.startIndex;
            }
            else if(seats[maxLine.endIndex]==0)
            {
                seats[maxLine.endIndex] = 1;
                return maxLine.endIndex;
            }
            else
            {
                seats[maxLine.startIndex + (maxLine.endIndex - maxLine.startIndex)/2] = 1;
                return maxLine.startIndex + (maxLine.endIndex - maxLine.startIndex)/2;
            }
        }
        else
        {
            Console.WriteLine("没有位置了");
        }
        return -1;
    }

    public void Leave(int p)
    {
        seats[p] = 0;
    }
}