team2012-E1-mysol-0023

从 Trac 迁移的文章

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

原文章内容如下：

{{{
/* 解题报告 //

题目要求在一条水平轴的整点 1, 2, .. , n 上选择 m 个点放置仓库
使得所有点到最近的仓库的距离之和最小，在此基础上选取字典序最小的解
选定仓库以后，让每个点将货物运输到最近的仓库里
如果有多个最近的则可以自选，问最小仓库容量是多少

如果确定了仓库的位置，后面的求容量显然可以简单的用二分加贪心来搞定
问题在于如何选择仓库的位置，如果想到了下面这种形式，就很容易了：
将 n - m 个空白位置，插入到 m 个仓库的前后侧

恩，关键点就是想到上面那个，其他没什么难的了

// By 猛犸也钻地 @ 2012.07.27 */
}}}

{{{
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int a[100000],s[100000];

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)==2){
        int l=(n-m)/(2*m),x=n-1;
        int c=(n-m)%(2*m);
        vector<int> u;
        for(int i=0;i<m;i++){
            x-=l+(2*i<c);
            u.push_back(x);
            x-=l+(2*i+1<c)+1;
        }
        reverse(u.begin(),u.end());
        for(int i=0;i<n;i++) scanf("%d",a+i);
        int lo=0,hi=100000005;
        while(lo<hi){
            int at=(lo+hi)/2,x=0,i=0;
            for(i=0;i<n;i++){
                if(x<m-1 && (u[x+1]-i<i-u[x]
                || (u[x+1]-i==i-u[x] && s[x]+a[i]>at))) x++;
                s[x]+=a[i];
                if(at<s[x]) break;
            }
            for(x=0;x<m;x++) s[x]=0;
            if(i<n) lo=at+1; else hi=at;
        }
        printf("%d\n",lo);
    }
}
}}}

/* 解题报告 //
题目要求在一条水平轴的整点 1, 2, .. , n 上选择 m 个点放置仓库
使得所有点到最近的仓库的距离之和最小，在此基础上选取字典序最小的解
选定仓库以后，让每个点将货物运输到最近的仓库里
如果有多个最近的则可以自选，问最小仓库容量是多少
如果确定了仓库的位置，后面的求容量显然可以简单的用二分加贪心来搞定
问题在于如何选择仓库的位置，如果想到了下面这种形式，就很容易了：
将 n - m 个空白位置，插入到 m 个仓库的前后侧
恩，关键点就是想到上面那个，其他没什么难的了
// By 猛犸也钻地 @ 2012.07.27 */

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[100000],s[100000];
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)==2){
        int l=(n-m)/(2*m),x=n-1;
        int c=(n-m)%(2*m);
        vector<int> u;
        for(int i=0;i<m;i++){
            x-=l+(2*i<c);
            u.push_back(x);
            x-=l+(2*i+1<c)+1;
        }
        reverse(u.begin(),u.end());
        for(int i=0;i<n;i++) scanf("%d",a+i);
        int lo=0,hi=100000005;
        while(lo<hi){
            int at=(lo+hi)/2,x=0,i=0;
            for(i=0;i<n;i++){
                if(x<m-1 && (u[x+1]-i<i-u[x]
                || (u[x+1]-i==i-u[x] && s[x]+a[i]>at))) x++;
                s[x]+=a[i];
                if(at<s[x]) break;
            }
            for(x=0;x<m;x++) s[x]=0;
            if(i<n) lo=at+1; else hi=at;
        }
        printf("%d\n",lo);
    }
}