【2019.11.11】

购物

二分 考场上想到了来着 被后面搜索劝退

ll cnt,b[N<<1];
bool check(ll mid){
    cnt=b[b[0]=1]=0;
    for(int i=1;i<=n;++i) {
        while(b[0]&&b[b[0]]+a[i]>mid) --b[0];
        if(!b[0]) return 0;
        for(int j=1;j<=b[0];++j) b[j+b[0]]=a[i]+b[j],++cnt;b[0]<<=1;
        if(cnt>=K) return 1;
        sort(b+1,b+b[0]+1);
    }
    return 0;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    rd(n),rd(K);
    for(int i=1;i<=n;++i) rd(a[i]),sum+=a[i];
    sort(a+1,a+1+n);
    ll l=1,r=sum,ans,mid;
    while(l<=r){
        mid=l+r>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%lld",ans);
    return 0;
}

收益

不想打

排列交换

嘤 记得考试到最后啥都想不出来了就把暴力覆盖全部数据范围 万一还能过几个点呢QAQ 知道万一后面数据水的话能多水点分可是我就是没有加上去QAQ

void pup(int o){t[o]=Min(t[ls],t[rs]);}
int query(int o,int l,int r,int x,int y){
    //if(l>y||r<x) return inf;
    if(x<=l&&r<=y) return t[o];
    int mid=l+r>>1;
    if(y<=mid) return query(ls,l,mid,x,y);
    if(x>mid) return query(rs,mid+1,r,x,y);
    return min(query(ls,l,mid,x,y),query(rs,mid+1,r,x,y));
}
void upd(int o,int l,int r,int x,int k){
    if(l==r){t[o]=k;return;}
    int mid=l+r>>1;
    if(x<=mid) upd(ls,l,mid,x,k);
    else upd(rs,mid+1,r,x,k);
    pup(o);
}

priority_queue<int>q;vector<int>e[N];
int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    rd(n),rd(K);
    for(int i=1;i<=n;++i) rd(a[i]),b[a[i]]=i;
    memset(t,inf,sizeof(t));
    for(int i=n,x,k;i;--i){
        k=b[i],x=query(1,1,n,k-K+1,k);
        if(x<=n) e[b[x]].push_back(k),++in[k];
        x=query(1,1,n,k,k+K-1);
        if(x<=n) e[b[x]].push_back(k),++in[k];
        upd(1,1,n,k,i);
    }
    for(int i=1;i<=n;++i) if(!in[i]) q.push(i);
    for(int i=n,u;i;--i){
        a[i]=u=q.top(),q.pop();
        for(int i=0,v,sz=e[u].size();i<sz;++i) if(!--in[v=e[u][i]]) q.push(v);
    }
    for(int i=1;i<=n;i++) b[a[i]]=i;
    for(int i=1;i<=n;++i) printf("%d\n",b[i]);
    return 0;
}

85昏

    void work(){
        for(int i=1;i<=n;++i) b[a[i]]=i;a[0]=b[0]=0,a[n+1]=b[n+1]=n+1;
        bool use=1;
        while(use){
            use=0;
            for(int i=1,nw,pre,nxt;i<=n;++i){
                nw=a[i],pre=nw-1,nxt=nw+1;
                if(b[pre]-b[nw]>=K) a[b[pre]]=nw,a[b[nw]]=pre,swap(b[pre],b[nw]),use=1;
                if(b[nw]-b[nxt]>=K) a[b[nxt]]=nw,a[b[nw]]=nxt,swap(b[nxt],b[nw]),use=1;
            }
        }
        for(int i=1;i<=n;++i) printf("%d\n",a[i]);
        exit(0);
    }
int main(){
//  freopen("swap.in","r",stdin);
//  freopen("swap.out","w",stdout);
    rd(n),rd(K);
    for(int i=1;i<=n;++i) rd(a[i]);
    if(K==1){for(int i=1;i<=n;++i) printf("%d\n",i);return 0;}
    if(K==n-1){
        if(a[1]>a[n]) swap(a[1],a[n]);
        for(int i=1;i<=n;++i) printf("%d\n",a[i]);return 0;
    }
    work();
    return 0;
}