2012-A3-0023

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意：此题可以分解为两个题：

1.N个点等距分别在一直线上，从中选取M个点标记为W，使所有点到最近的W的距离（W到最近的W距离为0）之和最小，若有多种方案使字典序最小。

2.上述N个点每个点有Xi的货，需要允到最近的W（如果有多个选其一），所有W的容量的最大值最小是多少。

对于1问，M个W，显然最多只能使M个点距离为0，2M个点距离为1，2M个点距离为2,2M个点距离为3...

所以距离和最小的方案，N个点要有M个距离为0，2M个距离为1,....2M个距离为L,L=(N-M)/(2M),当然最后剩下的N-(2L+1)*M个凑不够2M个的距离为L+1，

为了使字典序最小，所以选取方案，就把最后的那些增加距离。

这样方案就是前若干个管辖2L+1个点，有1或0个W管辖2L+2个点，最后若干个W管辖2L+3个点。

对于2问，在上述方案下，每个点到最近的W选取几乎是唯一的，

只有一种例外，前若干个管辖2L+1个点，后若干个W管辖2L+3个点，2L+3的W中的最先一个，可以考虑之前的2L+1的W，其他运完后，把它运到较少的那家就可以了

这样就可以几乎已读入复杂度解决这个问题了。

{{{
#include<cstdio>
typedef unsigned u32;
u32 sum(u32 c){
    u32 ret=0,t;
    for(;c--;ret+=t)scanf("%u",&t);
    return ret;
}
u32 a;
void ck(u32 y){if(y>a)a=y;}
int main(){
    for(u32 n,m;scanf("%u%u",&n,&m)==2;printf("%u\n",a)){
        u32 l=(n-m)/(m*2),r=n-m-(l*m<<1);
        //(l*2+1)*(m-(r+1)/2) (l*2+2)*(r%2) (l*2+3)*(r/2)
        u32 x1=m-(r+1>>1),t,e=l<<1|1;
        for(u32 i=a=0;i<x1;++i)ck(t=sum(e));
        if(r&1)ck(sum(l+1<<1));
        else if(x1&&r>1){
            u32 e=sum(1),h=sum(l+1<<1);r-=2;
            ck(h>t?t+e:h+e);ck(h);
        }
        e=l+1<<1|1;
        for(r>>=1;r--;)ck(sum(e));
    }
    return 0;
}
}}}

题意：此题可以分解为两个题：

1.N个点等距分别在一直线上，从中选取M个点标记为W，使所有点到最近的W的距离（W到最近的W距离为0）之和最小，若有多种方案使字典序最小。

2.上述N个点每个点有Xi的货，需要允到最近的W（如果有多个选其一），所有W的容量的最大值最小是多少。

对于1问，M个W，显然最多只能使M个点距离为0，2M个点距离为1，2M个点距离为2,2M个点距离为3...

所以距离和最小的方案，N个点要有M个距离为0，2M个距离为1,....2M个距离为L,L=(N-M)/(2M),当然最后剩下的N-(2L+1)*M个凑不够2M个的距离为L+1，

为了使字典序最小，所以选取方案，就把最后的那些增加距离。

这样方案就是前若干个管辖2L+1个点，有1或0个W管辖2L+2个点，最后若干个W管辖2L+3个点。

对于2问，在上述方案下，每个点到最近的W选取几乎是唯一的，

只有一种例外，前若干个管辖2L+1个点，后若干个W管辖2L+3个点，2L+3的W中的最先一个，可以考虑之前的2L+1的W，其他运完后，把它运到较少的那家就可以了

这样就可以几乎已读入复杂度解决这个问题了。

#include<cstdio>
typedef unsigned u32;
u32 sum(u32 c){
    u32 ret=0,t;
    for(;c--;ret+=t)scanf("%u",&t);
    return ret;
}
u32 a;
void ck(u32 y){if(y>a)a=y;}
int main(){
    for(u32 n,m;scanf("%u%u",&n,&m)==2;printf("%u\n",a)){
        u32 l=(n-m)/(m*2),r=n-m-(l*m<<1);
        //(l*2+1)*(m-(r+1)/2) (l*2+2)*(r%2) (l*2+3)*(r/2)
        u32 x1=m-(r+1>>1),t,e=l<<1|1;
        for(u32 i=a=0;i<x1;++i)ck(t=sum(e));
        if(r&1)ck(sum(l+1<<1));
        else if(x1&&r>1){
            u32 e=sum(1),h=sum(l+1<<1);r-=2;
            ck(h>t?t+e:h+e);ck(h);
        }
        e=l+1<<1|1;
        for(r>>=1;r--;)ck(sum(e));
    }
    return 0;
}