P1489 猫狗大战【洛谷算法习题】-开发者社区

P1489 猫狗大战

网页链接

P1489 猫狗大战

题目描述

新一年度的猫狗大战通过 SC（星际争霸）这款经典的游戏来较量，野猫和飞狗这对冤家为此已经准备好久了，为了使战争更有难度和戏剧性，双方约定只能选择 Terran（人族）并且只能造机枪兵。

比赛开始了，很快，野猫已经攒足几队机枪兵，试探性的发动进攻；然而，飞狗的机枪兵个数也已经不少了。野猫和飞狗的兵在飞狗的家门口相遇了，于是，便有一场腥风血雨和阵阵惨叫声。由于是在飞狗的家门口，飞狗的兵补给会很快，野猫看敌不过，决定撤退。这时飞狗的兵力也不足够多，所以没追出来。

由于不允许造医生，机枪兵没办法补血。受伤的兵只好忍了。

现在，野猫又攒足了足够的兵力，决定发起第二次进攻。为了使这次进攻给狗狗造成更大的打击，野猫决定把现有的兵分成两部分，从两路进攻。由于有些兵在第一次战斗中受伤了，为了使两部分的兵实力平均些，分的规则是这样的：

两部分兵的个数最多只能差一个；
每部分兵的血值总和必须要尽可能接近。

现在请你编写一个程序，给定野猫现在有的兵的个数以及每个兵的血格值，求出野猫按上述规则分成两部分后每部分兵的血值总和。

输入格式

第一行为一个整数n ( 1 ≤ n ≤ 200 ) n\ (1 \le n \le 200)n(1≤n≤200)，表示野猫现在有的机枪兵的个数。以下的n nn行每行一个整数，表示每个机枪兵的血格( 1 ≤ a i ≤ 40 ) (1 \le a_i \le 40)(1≤ai≤40)。

输出格式

一行，为两个整数，表示分成两部分后每部分兵的血值总和。要求输出的第一部分兵的血量总和不大于第二部分兵的血量总和。

输入输出样例 #1

输入 #1

3 35 20 32

输出 #1

35 52

说明/提示

TO 狗狗：这道题的数据范围我已经尽量按星际的游戏规则来了，如果你再固执于由于机枪兵的攻击力一定使不能达到某些血格值或者游戏中一定要造农民不能使机枪兵的人数达到200 200200的话，我只能决定将那场猫狗大战的录像公开于世人了！！！

解题思路

本题是0/1 背包 + 分组均衡的经典题型。要求将n nn个兵分成两组，使得两组人数最多差一个，并且两组血量总和尽可能接近。可以将问题转化为：从n nn个数中选出恰好⌊ n / 2 ⌋ \lfloor n/2 \rfloor⌊n/2⌋个数，使其和尽可能接近总和的一半。

1. 问题等价转化

两组人数最多差一个，即一组人数为⌊ n / 2 ⌋ \lfloor n/2 \rfloor⌊n/2⌋，另一组为n − ⌊ n / 2 ⌋ n - \lfloor n/2 \rfloorn−⌊n/2⌋，当n nn为奇数时差1 11。
设总血量为t o t a l totaltotal，若选出的⌊ n / 2 ⌋ \lfloor n/2 \rfloor⌊n/2⌋个兵的血量和为S SS，则另一组的血量和为t o t a l − S total - Stotal−S。
为了使两部分血量和尽可能接近，只需让S SS尽可能接近t o t a l / 2 total/2total/2。
因此问题转化为：在n nn个数中选出恰好k = ⌊ n / 2 ⌋ k = \lfloor n/2 \rfloork=⌊n/2⌋个数，求能组成的最接近t o t a l / 2 total/2total/2的和。

2. 算法实现：二维 0/1 背包

状态定义：dp[i][j]表示从前若干个兵中选出恰好i ii个，能否组成血量和j jj（1表示能，0表示不能）。
初始化：dp[0][0] = 1，其余为0。
转移方程：对于每个兵的血量a k a_kak，逆序更新数量i ii和血量j jj：
```
dp[i][j] |= dp[i-1][j-a[k]]
```
即如果不选当前兵，则状态不变；如果选，则从前i − 1 i-1i−1个、血量和j − a [ k ] j-a[k]j−a[k]的状态转移过来。
容量与数量上限：i ii最大枚举到k = ⌊ n / 2 ⌋ k = \lfloor n/2 \rfloork=⌊n/2⌋，血量总和最大为200 × 40 = 8000 200 \times 40 = 8000200×40=8000。
寻找最优解：遍历所有可能的血量和j jj，若dp[k][j]为真，计算两组血量差∣ 2 j − t o t a l ∣ |2j - total|∣2j−total∣，取差值最小的j jj作为答案。
输出：按题目要求，先输出较小的血量和，再输出较大的血量和。

3. 复杂度分析

时间复杂度：背包三层循环，兵数n ≤ 200 n \le 200n≤200，血量上限8000 80008000，数量上限k ≤ 100 k \le 100k≤100，总操作量约200 × 100 × 8000 ≈ 1.6 × 10 8 200 \times 100 \times 8000 \approx 1.6 \times 10^8200×100×8000≈1.6×108，在可接受范围内（使用布尔位运算可优化常数）。
空间复杂度：O ( k × maxSum ) ≈ 100 × 8000 O(k \times \text{maxSum}) \approx 100 \times 8000O(k×maxSum)≈100×8000，完全可行。

总结

将人数和血量双重约束转化为二维 0/1 背包，求解恰好选出k kk个数时最接近总和一半的血量和。最后根据最优S SS输出两组的血量和。该方法直观且数据范围下效率足够。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n;ll a[205];ll dp[205][8005];ll total;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(ll i=1;i<=n;i++){cin>>a[i];total+=a[i];}dp[0][0]=1;for(ll k=1;k<=n;k++){for(ll i=n/2+1;i>=1;i--){for(ll j=8000;j>=a[k];j--){dp[i][j]=(dp[i][j]|dp[i-1][j-a[k]]);}}}ll ans=0;ll diff=INF;for(ll j=0;j<=8000;j++){if(dp[n/2][j]){ll cur=llabs(2*j-total);if(cur<diff){diff=cur;ans=j;}}}cout<<min(ans,total-ans)<<' '<<max(ans,total-ans)<<endl;return0;}