team2012-F3-sol-0023

从 Trac 迁移的文章

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

原文章内容如下：

{{{
题意：给定n个数组成的一个序列，要选出m个特殊位置，使得剩下的所有数到距其最近的特殊位置之和最小，如果有多种方案取字典序最小的
然后要使得所有数移到最近的特殊位置，求最小的容量。
解法：由题意，选取特殊位置的构造法必然要将这n个数划分成m个组：
1，取一个最大奇数k，使得 k * m <= n，先给每个组放k个数
2，若余下 r = n - k * m，则从后往前，每个组放2个
3，若余下一个，则放在那个组的末尾
最后形如：
**_** **_** ***_*** ***_*** 或者 **_** **_*** ***_*** ***_***
在第一种情况里，有一个位置到两边都存在最近距离的，要特殊记录一下
然后二分容量，从左到右贪心地测试即可
}}}
{{{
#include <iostream>
#include <cstdio>
using namespace std;

int a[100004], group[100004], spg, m, n;

bool test(int c)
{
    int p = 0, sum = 0, i, j;
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=group[i];j++)
        {
            sum += a[p+j];
            if(sum > c)
                return 0;
        }
        if(i == spg)
        {
            sum += a[p+j];
            if(sum > c)
                sum = 0;
            else
                sum = -a[p+j];
        }
        else
            sum = 0;
        p += group[i];
    }
    return 1;
}

int gao()
{
    int low = 0, high = 100000002;
    while(low < high)
    {
        int mid = (low+high) / 2;
        if(test(mid))
            high = mid;
        else
            low = mid + 1;
    }
    return low;
}

int main()
{
    while(~scanf("%d %d", &n, &m))
    {
        for(int i=1;i<=n;i++)
            scanf("%d", a+i);

        int com = n / m;
        if(com%2 == 0)
            com--;
        for(int i=1;i<=m;i++)
            group[i] = com;
        int rest = n - com*m;
        if(rest%2 == 0)
        {
            rest /= 2;
            for(int i=m;i>m-rest;i--)
                group[i]+=2;
            spg = m-rest;
        }
        else
        {
            rest /= 2;
            for(int i=m;i>m-rest;i--)
                group[i]+=2;
            group[m-rest]++;
            spg = -1;
        }

        printf("%d\n", gao());
    }
    return 0;
}
}}}

题意：给定n个数组成的一个序列，要选出m个特殊位置，使得剩下的所有数到距其最近的特殊位置之和最小，如果有多种方案取字典序最小的
然后要使得所有数移到最近的特殊位置，求最小的容量。
解法：由题意，选取特殊位置的构造法必然要将这n个数划分成m个组：
1，取一个最大奇数k，使得 k * m <= n，先给每个组放k个数
2，若余下 r = n - k * m，则从后往前，每个组放2个
3，若余下一个，则放在那个组的末尾
最后形如：
**_** **_** ***_*** ***_*** 或者 **_** **_*** ***_*** ***_***
在第一种情况里，有一个位置到两边都存在最近距离的，要特殊记录一下
然后二分容量，从左到右贪心地测试即可

#include <iostream>
#include <cstdio>
using namespace std;
int a[100004], group[100004], spg, m, n;
bool test(int c)
{
    int p = 0, sum = 0, i, j;
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=group[i];j++)
        {
            sum += a[p+j];
            if(sum > c)
                return 0;
        }
        if(i == spg)
        {
            sum += a[p+j];
            if(sum > c)
                sum = 0;
            else
                sum = -a[p+j];
        }
        else
            sum = 0;
        p += group[i];
    }
    return 1;
}
int gao()
{
    int low = 0, high = 100000002;
    while(low < high)
    {
        int mid = (low+high) / 2;
        if(test(mid))
            high = mid;
        else
            low = mid + 1;
    }
    return low;
}
int main()
{
    while(~scanf("%d %d", &n, &m))
    {
        for(int i=1;i<=n;i++)
            scanf("%d", a+i);
        int com = n / m;
        if(com%2 == 0)
            com--;
        for(int i=1;i<=m;i++)
            group[i] = com;
        int rest = n - com*m;
        if(rest%2 == 0)
        {
            rest /= 2;
            for(int i=m;i>m-rest;i--)
                group[i]+=2;
            spg = m-rest;
        }
        else
        {
            rest /= 2;
            for(int i=m;i>m-rest;i--)
                group[i]+=2;
            group[m-rest]++;
            spg = -1;
        }
        printf("%d\n", gao());
    }
    return 0;
}