「题目描述」

小 B 是一个电影迷，只要有时间，她就要去观摩最新的大片。但她不喜欢自己在电脑或其他电子设备上观看，而是喜欢去电影院，因为她觉得那里更有气氛。由于工作关系，小 B 这次被派到 A 地一段时间，她发现这里的电影院和她熟悉的模式完全不同。电影院内部都是正方形的，一共有 k 排，从前到后按照 1 到 k 编号，每排内有 k个座位，从左到右按照 1 到 k 编号，其中 k 为奇数。考虑到安全因素，座位不允许购票者自行挑选，而是由售票人员通过电脑程序确定。由于大家都希望有更好的观影效果，因此一般都倾向于选择更靠近影院中心的座位。电脑程序选择座位的过程为：如果有人需要购买 m 张电影票，程序首先会确定一个排号 x，并从中选择一段连续且尚未售出的座位号 [l,r] ，其中 r - l + 1 = m 。如果没有任何一排中有 m 个连续的空座位，则电脑程序会报错，在这个购票请求中将不会卖出任何票。在保证选出的座位在同一排且座位号连续的前提下，程序会选择最“接近中心”的座位。具体来说，令 x(c) = y(c) = k+12 ，表示影院中最中心的座位。定义选出的这些座位到影院中心的距离函数为：

image.png

最“接近中心”的座位为能最小化上述函数的座位。若有多个可选座位均满足离影院中心距离最小的条件，则选座程序优先选择靠前的座位（即排号 x 最小的座位）。若仍有多个座位符合要求，则选座程序优先选择靠左的座位（即座位号 l 值最小的座位）。假设电影院最开始没有售出任何座位，小 B 希望知道对于给出的 n 个购票请求，每次售出的票都能买到哪些座位？

「输入描述」

输入包含多组数据，你需要用判断是否读到文件末尾的形式判断输入是否结束。每组数据的第一行包含两个正整数 n 和 k，表示购票请求的数量和影院大小。保证1 ≤ n ≤ 300000, 1 ≤ k ≤ 300001，且 k 为奇数。第二行为空格分隔的 n 个正整数，其中第 i（1 ≤ i ≤ n）个数为 mi，表示每次要求购买的票数，保证 1 ≤ mi ≤ k。 

「输出描述」

每组数据输出包含 n 行，每个购买请求的结果为一行。如果无法在一排中买到 mi 个连续的座位，则在对应的行中输出 1。否则输出三个空格分隔的整数 x, l,r，为所买电影票的排号和起止座位号。

「样例输入」

2 1

1 1

4 3

1 2 3 1

「样例输出」

1 1 1

-1

2 2 2

1 1 2

3 1 3

2 1 1

「子任务」

对于 20% 的测试数据，n ≤ 50, k ≤ 25;

对于 40% 的测试数据，n ≤ 100, k ≤ 101;

对于 50% 的测试数据，n ≤ 1000, k ≤ 501;

对于 60% 的测试数据，n ≤ 1000, k ≤ 1001;

对于 70% 的测试数据，n ≤ 50000, k ≤ 50001;

对于 80% 的测试数据，n ≤ 100000, k ≤ 100001;

对于 90% 的测试数据，n ≤ 200000, k ≤ 200001;

对于 100% 的测试数据，n ≤ 300000, k ≤ 300001，保证每个测试点的数据组数不超过 5 组。

「初步题解」

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<fstream>
#include<math.h>

using namespace std;

const int K=300002;
const int N=300001;
//因为要尽量往中间坐，所以每排只要有人必定连座
//L[i]：从中间往两边指向左边第一个空位置，R[i]同理。
int L[K],R[K],n,k,s,x,start,end,l,r,temp;

//求距离之和
int dis(int x,int l,int r){
    int sum=0,f=(k+1)/2;
    for(int i=l;i<=r;i++)
        sum+=(abs(f-x)+abs(f-i));
    return sum;
}

//根据条件选择更优座位
void getseat(int &temp,int &i,int &s,int &x,int &l,int &r,int &start,int &end){
    temp=dis(i,start,end);
    if (temp<s)
        s=temp,x=i,l=start,r=end;
    else if (temp==s&&i<x)
        x=i,l=start,r=end;
    else if (temp==s&&i==x&&start<l)
        l=start,r=end;
}

int main(){
    while(cin >> n >> k){
        for(int i=1;i<=k;i++){
            L[i]=(k+1)/2;
            R[i]=(k+1)/2;
        }
        while(n--){
            int m, start, end;
            s=0x7fffffff; //int类型中最大的数
            cin >> m;
            for(int i=1;i<=k;i++){
                //如果选择奇数个座位 且 该行座位均为空闲状态
                if(L[i]==R[i]&&(m&1)){
                    start=(k+1)/2-(m+1)/2+1; end=(k+1)/2-(m+1)/2+m;
                    getseat(temp,i,s,x,l,r,start,end);
                //如果选择偶数个座位 且 该行座位均为空闲状态
                }else if(L[i]==R[i]){
                    start=(k+1)/2-m/2; end=(k+1)/2+m/2-1;
                    getseat(temp,i,s,x,l,r,start,end);
                //如果可选座位在左边
                }else if(L[i]>=m){
                    start=L[i]-m+1; end=L[i];
                    getseat(temp,i,s,x,l,r,start,end);
                //如果可选座位在右边
                }else if(R[i]+m-1<=k){
                    start=R[i]; end=R[i]+m-1;
                    getseat(temp,i,s,x,l,r,start,end);
                }
            }
            if(s==0x7fffffff){
                printf("-1\n");
                continue;
            }
            //更新L,R
            L[x]=min(L[x],l-1);
            R[x]=max(R[x],r+1);
            printf("%d %d %d\n",x,l,r);
        }
    }
    return 0;
}

A Student on the way to full stack of Web3.