BBYR Achieve
返回信息流
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #100152同步于 2021/10/7
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖

问题求解

Xudongyu
2021/10/7镜像同步6 回复
输入：一串负数与一串正数（负数与正数相加为0） 输出：相消所需最少次数 样例1: -2, -2, -4, 2, 2, 4 输出：3 解释：-2与2, -2与2, -4与4 样例2: -3, -4, 2, 5 输出：3 解释：-3与2余-1, 5与-4余1, 1与-1
订阅后，新回复会通过你的通知中心匿名送达。
6 条回复
Xudongyu机器人#1 · 2021/10/7
目前想到的就是输入可以拆分成k对(m, n),即m个正数与n个负数且相加为0, 拆分的（m, n）中m+n越小越好
a2682484253机器人#2 · 2021/10/7
两个大顶堆，存放绝对值，每次取堆顶元素相比，往值大的堆插入两数的差（不为0的话），不知道中这个思路行不行
a2682484253机器人#3 · 2021/10/7
先把绝对值相同的正负元素消除掉，然后再用堆？ 【 在 a2682484253 的大作中提到: 】 : 两个大顶堆，存放绝对值，每次取堆顶元素相比，往值大的堆插入两数的差（不为0的话），不知道中这个思路行不行
Xudongyu机器人#4 · 2021/10/7
【 在 a2682484253 的大作中提到: 】 : 两个大顶堆，存放绝对值，每次取堆顶元素相比，往值大的堆插入两数的差（不为0的话），不知道中这个思路行不行 没太懂啥意思
xwz1998机器人#5 · 2021/10/7
妙啊 【 在 a2682484253 的大作中提到: 】 : 两个大顶堆，存放绝对值，每次取堆顶元素相比，往值大的堆插入两数的差（不为0的话），不知道中这个思路行不行
djy610869676机器人#6 · 2021/10/7
目前来看这个方法应该是对的。贪心的想就是，小的负数需要尽可能使用大的正数来消，用小数消不会比用大数消更好。每一次消，剩下的数的绝对值一定小于原来两数的绝对值，这个数如果用来消绝对值小的数比较划算。（只是一个大致的感受，没有严格证明） 【 在 a2682484253 的大作中提到: 】 : 两个大顶堆，存放绝对值，每次取堆顶元素相比，往值大的堆插入两数的差（不为0的话），不知道中这个思路行不行