小红拿到了一个数组,她准备选择若干元素乘以 -1,使得最终所有元素的和为 0。小红想知道最少需要选择多少个元素?

输入格式:

第一行输入一个正整数 n,代表数组的大小。 第二行输入 n 个整数 a,代表数组的元素。

其中,$1 \leq n \leq 200, -200 \leq a \leq 200$。

输出格式:

如果无法使得最终所有元素之和为 0,则输出 -1。 否则输出一个整数,代表选择元素的最小数量。

输入样例:

3
1 -2 3

输出样例:

1

输入样例说明:

选择第一个元素即可。

输入样例:

3
2 -2 3

输出样例:

-1

题目分析

典型的01背包,但是我比赛的时候没看出来(

首先,虽然数组的大小很小,但是 DFS 肯定会 TLE。

我们尝试分析:

要对一个数组内的若干元素乘 -1, 使得所有元素的和为 0。那么,一定存在 $$ 正数之和 + 负数之和 = 0 $$ 那么问题就简单了。

  • abs(正数之和 - |负数之和|) = 0 :那么不需要将任何元素乘以 -1。
  • abs(正数之和 - |负数之和|) != 0 :我们接着分析

如果正数之和和负数之和直接存在差值,我们假设正数之和大于|负数之和|:

那么我们应该从正数中选取 和为 Sum 的组合乘 -1,很显然: $$ Sum =abs(正数之和 - |负数之和|) / 2 $$ 也就是说, 如果

  • abs(正数之和 - |负数之和|)
  • abs(正数之和 - |负数之和|) = 0 :存在这种组合

题目我们已经分析完了。

那么怎么得到构成 Sum 的组合的最小元素个数呢? 因为 n 的数据范围很小,所以我们可以在读入数据的时候, 维护一个哈希表,键为 Sum,值为最小元素个数,将所有的Sum都存下来即可。(这里其实就是一个 DP)

除了这种分析出来的依赖数据量的偏暴力做法,其实也可以将这道题转化为 01 背包问题,或者线性 DP。

代码实现

#include <iostream>
#include <unordered_map>
#define x first 
#define y second
using namespace std;
using LL = long long;

int n;
LL t, sumP, sumN;
unordered_map<LL, int> pos, neg;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    pos[0] = 0; neg[0] = 0;
    for (int i = 0; i < n; ++i) {
        cin >> t;
        if (t > 0) {
            sumP += t;
            unordered_map<LL, int> pos_new = pos;
            for (const auto &p : pos) {
                if (pos_new[p.x + t]) pos_new[p.x + t] = min(pos_new[p.x + t], p.y + 1);
                else pos_new[p.x + t] = p.y + 1;
            }
            pos = pos_new;

        } else if (t < 0) {
            t = -t;
            sumN += t;
            unordered_map<LL, int> neg_new = neg;
            for (const auto &p : neg) {
                if (neg_new[p.x + t]) neg_new[p.x + t] = min(neg_new[p.x + t], p.y + 1);
                else neg_new[p.x + t] = p.y + 1;
            }
            neg = neg_new;
        }
    }

    if (sumP == sumN) cout << "0";
    else {
        LL dif = sumP - sumN;
        if (dif
        else if (sumP > sumN) cout << (pos[dif >> 1] ? pos[dif >> 1] : -1);
        else cout << (neg[dif >> 1] ? neg[dif >> 1] : -1);
    }    
    return 0;
}
分类: DFSDPThought

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status