CCSP2016-1 选座（ticket_chooser）

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

最 ‘‘接近中心’’ 的座位为能最小化上述函数的座位。若有多个可选座位均满足离影 院中心距离最小的条件，则选座程序优先选择靠前的座位（即排号 x 最小的座位）。若 仍有多个座位符合要求，则选座程序优先选择靠左的座位（即座位号 l 值最小的座位）。 假设电影院最开始没有售出任何座位，小 B 希望知道对于给出的 n 个购票请求， 每次售出的票都能买到哪些座位？
【输入描述】
输入包含多组数据，你需要用判断是否读到文件末尾的形式判断输入是否结束。 每组数据的第一行包含两个正整数 n 和 k，表示购票请求的数量和影院大小。保证 1≤n≤300,000,1≤k≤300,001，且 k 为奇数。 第二行为空格分隔的 n 个正整数，其中第 i（1 ≤i≤n）个数为 mi，表示每次要求 购买的票数，保证 1≤mi ≤k。
【输出描述】
每组数据输出包含 n 行，每个购买请求的结果为一行。0 如果无法在一排中买到 mi 个连续的座位，则在对应的行中输出 −1。否则输出三个 空格分隔的整数 x,l,r，为所买电影票的排号和起止座位号。
【样例 1 输入】
2 1
1 1
4 3
1 2 3 1
【样例 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(){  
    ifstream ifile("1in.txt");  
    while(1){  
        ifile>>n>>k;  
        if(ifile.eof())  
            break;  
        for(int i=1;i<=k;i++){  
            L[i]=(k+1)/2;  
            R[i]=(k+1)/2;  
        }  
        while(n--){  
            int m;  
            s=0x7fffffff;  
            ifile>>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);  
                }  
                if(L[i]>=m){  
                    start=L[i]-m+1; end=L[i];  
                    getseat(temp,i,s,x,l,r,start,end);  
                }  
                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[x]=min(L[x],l-1);//可能落座在右半边，所以要与原值比较   
            R[x]=max(R[x],r+1);  
            printf("%d %d %d\n",x,l,r);  
        }  
    }  
    return 0;   
}