Peace

题目描述

阿汤同学为了准备下学期的 ACM-ICPC，刷了很多的题目，他觉得自己已经比较厉害了，于是想出个题目考考你。现在他给你一个数组 A，问你是否能将该数组划分成数组 B、C 使得 B 数组的平均数和C 数组的平均数相等，数组 B 和 C 都不能为空。

输入描述:

从标准输入读入数据。
输入包含多组数据，第一行一个整数 T 代表数据组数。接下来依次描述每组数据，对于每组数据：
第一行输入正整数 N，第二行输入 N 个非负整数

1≤|A|≤30 （数组 A 的长度范围在 1 到 30 之间 ）
0≤A[i]≤10000 （数组 A 中的元素）

输出描述:

输出到标准输出。
对于每组数据，输出一行：
如果能划分成满足题目要求的数组 B 和 C 则输出 yes，否则输出no

输入

1
8
1 2 3 4 5 6 7 8

输出

yes

说明

样例说明：将数组 A 划分成【1,4,5,8】和【2,3,6,7】,平均数为 4.5

思路

1. 数组A可以分成两个平均数相同的数组B 和 C，也就是在A中找一个数组，使得这个数组的平均数是整个数组的平均数。
   DP：dp[ K ] [ Z ] : Z 表示已经选了几个数， K表示当前数组的和。如果K / Z == Average 就是yes，否则no。
2. 设数组A的和为SumA，长度为N，B的和为SumB，长度为M 则需满足条件： （SumA-SumB） / （N-M） = sumB / M；
   即可得到数组B 和数组A的平均数相等，所以我们可以对数组A中的元素减 去数组A的平均值，问题转化为在数组A中找到一个数组B使得数组B的和为0.显 然的做法是枚举A中数字的所有可能的组合，但是因为A的长度多达30, 230会超 时，所以考虑拆分成两个部分，每一边最多15个元素，复杂度变成 215，然后二 分在两边找答案就可以了。

AC

#include<bits/stdc++.h>
#define N 300005
#define mem(a, b) memset(a, b, sizeof(a))
#define ll long long
using namespace std;
const double eps = ;
bool dp[N][];
int a[], n, MAX;
double ave;
int solve () {
//  if (n == 1) return 0;
//  i 即将放入背包的元素 
    for (int i = ; i <= n; i++) {
//      j 已经放入背包的元素总和 
        for (int j = MAX; j >= ; j--) {
//          k 已经放入背包的元素个数 
//          k < n - 1, 因为数组不为空，不能全部放入背包 
            for (int k = ; k < n - ; k++) {
//              如果放入背包元素合法，就放入新的元素 
                if (dp[j][k]) {
                    int temp = j + a[i];
                    MAX = max(temp, MAX);
                    dp[temp][k + ] = ;
                    if (abs(temp *  / (k + ) - ave) < eps)  return ;
                }
            }

        }
    }
    return ;   
}

int main() {
//  freopen("in.txt", "r", stdin);
    int t;
    scanf("%d", &t);
    while (t--) {
        ave = ;
        scanf("%d", &n);
        for (int i = ; i <= n; i++) {
            scanf("%d", &a[i]);
            ave += a[i];
        }
        ave /= n;
        mem(dp, );
        dp[][] = ;
        MAX = ;
        if (solve())    printf("yes\n");
        else    printf("no\n"); 
    }


    return ;
}