Codeforces 899C - Dividing the numbers

传送门：http://codeforces.com/contest/899/problem/C

本题是一个数学问题——集合划分。

将集合{1,2,...,n}划分成两个集合，使得两个集合的元素之和的绝对差值最小。

首先，考虑最简单的操作：

第1步：将元素1和n置入集合A；

第2步：将元素2和n-1置入集合B；

第3步：将元素3和n-2置入集合A；

……

第i步：将元素i和n+1-i，当i为奇数时置入集合A，偶数时置入集合B；

……

第n/2步：将元素n/2和n/2+1置入集合B。

如此，集合A中的元素之和与集合B中的元素之和相等，绝对差为0。

为保证第n/2步将元素置入集合B，则应保证n是4的整数倍。

于是，若n是4的整数倍，则划分的最小绝对差为0，集合A={1,n,3,n-2,...,n/2-1,n/2+2}，集合B={2,n-1,4,n-3,...,n/2,n/2+1}。

若n不可被4整除，则可以考虑预处理{1,2,...,n}的前若干项构成的集合{1,2,...,x}，之后再处理集合{x+1,...,n}。当然，为了使得集合{x+1,...,n}易于处理，应保证其项数n-x是4的整数倍。于是，x可以取n%4。

以下是按照x值分类的预处理过程：

①若x=1，则预处理{1}：将1置入集合A，此时最小绝对差为1；

②若x=2，则预处理{1,2}：将1置入集合A，2置入集合B，此时最小绝对差为1；

③若x=3，则预处理{1,2,3}：将1和2置入集合A，3置入集合B，此时最小绝对差为0。

之后，{x+1,...,n}的处理过程类似于最初提及的操作——可将集合{x+1,...,n}看作{1,...,n-x}中的每一个元素增加x得到的集合，其中n-x是4的整数倍。

参考程序如下：

#include <stdio.h>

#define MAX_N 30010

int a[MAX_N];

int main(void)

{

    int n;

    scanf("%d", &n);

    int x = n % ;

    int cnt = ;

    int dif;

    if (x == ) dif = ;

    else if (x == ) {

        dif = ;

        a[cnt++] = ;

    }

    else if (x == ) {

        dif = ;

        a[cnt++] = ;

    }

    else if (x == ) {

        dif = ;

        a[cnt++] = ;

        a[cnt++] = ;

    }

    for (int i = x + ; i <= x + (n - x) / ; i += ) {

        a[cnt++] = i;

        a[cnt++] = n + x +  - i;

    }

    printf("%d\n%d", dif, cnt);

    for (int i = ; i < cnt; i++)

        printf(" %d", a[i]);

    return ;

}

巴特西

Codeforces 899C - Dividing the numbers

最新文章

热门文章