中国大学生计算机系统与程序设计竞赛 CCF-CCSP-2016 选座（ ticket_chooser ）

选座（ ticket_chooser ）

 

不会正解，欢迎讨论

//60分

#include<cstdio>
#define max(a,b) (a)>(b)?a:b
#define min(a,b) (a)<(b)?a:b
const int N=3e5+5;
template <typename T>
inline void read(T &x){
    T f=1;register char ch=getchar();x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
inline int abs(int x){return x>0?x:-x;}
int n,k,L[N],R[N],tv,s,t,v,x,l,r;
inline int GetVal(const int &x,const int &l,const int &r){
    int res(0),mid=k+1>>1;
    for(int i=l;i<=r;i++) res+=abs(x-mid)+abs(i-mid);
    return res;
}
inline void GetPos(int &tv,const int &h,const int &s,const int &t,int &v,int &x,int &l,int &r){
    tv=GetVal(h,s,t);
    if(tv<v) v=tv,x=h,l=s,r=t;else
    if(tv==v&&h<x) x=h,l=s,r=t;else
    if(tv==v&&h==x&&s<l) x=h,l=s,r=t;
}
inline void Solve(){//L[x]表示x排从中间向左最早的空座 
    for(int i=1;i<=k;i++) L[i]=k+1>>1,R[i]=k+1>>1;
    for(int i=1,q;i<=n;i++){
        read(q);v=2e9;
        for(int j=1;j<=k;j++){//时间复杂度的瓶颈
        //有想：贪心从(k+1)/2排同时向上、向下迭代，但不知道停止的条件，以及正确性 
            if(L[j]==R[j]){
                if(q&1){
                    s=(k+1>>1)-(q+1>>1)+1,t=(k+1>>1)-(q+1>>1)+q,
                    GetPos(tv,j,s,t,v,x,l,r);
                }
                else{
                    s=(k+1>>1)-(q>>1),t=(k+1>>1)+(q>>1)-1,
                    GetPos(tv,j,s,t,v,x,l,r);
                }
            }
            if(L[j]>=q){
                s=L[j]-q+1,t=L[j],
                GetPos(tv,j,s,t,v,x,l,r);
            }
            if(R[j]+q-1<=k){
                s=R[j],t=R[j]+q-1,
                GetPos(tv,j,s,t,v,x,l,r);
            }
        }
        if(v==2e9){puts("-1");continue;}
        L[x]=min(L[x],l-1);
        R[x]=max(R[x],r+1);
        printf("%d %d %d
",x,l,r);
    }
}
int main(){
    while(~scanf("%d%d",&n,&k)) Solve();
    return 0;
}