Offer收割]编程练习赛50---座位问题

梦里梦外; 2022-05-29 04:05 130阅读 0赞

HIHO银行等待区有一排N个座位，从左到右依次编号1~N。现在有M位顾客坐在座位上，其中第i位坐在编号Ai的座位上。

之后又陆续来了K位顾客，(K + M ≤ N) 他们都会选择坐在最"舒适"的空座位上，并且过程中没有顾客离开自己的座位。

最"舒适"的定义是：

1. 对于一个座位，我们将它左边连续的空座位数目记作X，它右边连续的空座位数目记作Y。

2. 顾客首先会选择min(X, Y)最大的座位。

3. 如果有多个选择，顾客会选择其中max(X, Y)最大的座位。

4. 如果还是有多个选择，顾客会选择其中编号最小的座位。

请你计算出之后来的K位顾客坐在几号座位上。

### 输入 ###

第一行包含三个整数N，M和K。

第二行包含M个整数A1, A2, ... AM。

对于50%的数据，1 ≤ N ≤ 1000

对于100%的数据，1 ≤ N ≤ 100000,  1 ≤ Ai ≤ N,  K + M ≤ N

### 输出 ###

输出K行，每行一个整数代表该位顾客座位的编号。

样例输入

10 2 3  
    1 10

样例输出

#include <cstdlib>
    #include <cstdio>
    #include <queue>
    #include <algorithm>
    using namespace std;
    struct A{
        int id,l,r;
        friend bool operator < (A a,A b){
           if(a.r-a.l==b.r-b.l)
               return a.id>b.id;
           return a.r-a.l<b.r-b.l;    
        }
        
    }f[100010],x,y;
    int a[100010];
    int main(int argc, char *argv[])
    {
        int n,m,k,j;
        priority_queue<A> Q;
        scanf("%d %d %d",&n,&m,&k);
        a[0]=0;
        a[m+1]=n+1;
        for(int i=1;i<=m;i++)
             scanf("%d",&a[i]);
        sort(a+1,a+m+1);
        j=0;
        for(int i=1;i<=m+1;i++){
                if(a[i]-a[i-1]>1){
                   f[j].l=a[i-1];
                   f[j].r=a[i];
                   f[j].id=(a[i-1]+a[i])/2;
                   Q.push(f[j]);
                   j++;
                }
        }
        for(int i=0;i<k;i++){
                x=Q.top();
                Q.pop();
                printf("%d\n",x.id);
                y.l=x.l;
                y.r=x.id;
                y.id=(x.l+x.id)/2;
                if(y.r-y.l>1)
                   Q.push(y);
                y.l=x.id;
                y.r=x.r;
                y.id=(x.r+x.id)/2;
                if(y.r-y.l>1)
                   Q.push(y);
        }
        system("PAUSE");
        return EXIT_SUCCESS;
    }