求助一道题

学术版

Deuteron @ 2022-10-15 12:11:08

RT

给定一个大小为 n 集合，你要把集合删空

有以下两种操作：

若 $x\ne y$ 则付出 $x-y$ 的绝对值的代价将 $x,y$ 中较小的删除 $2.$ 选择一个数 $x$ 付出 $x$ 的代价将 $x$ 删除 求最小代价

by go_deeper @ 2022-10-15 12:21:35

假设有两个不同的数字 x,y 且 x<y，那么删除这两个数字的代价应该是 min(2y-x,x+y) 。

所以贪心即可。

我感觉的，不一定对。

by Kreado @ 2022-10-15 12:39:05

考虑贪心，首先将原数组每两个相同的元素消除在排序，ans=min(a[i-1],a[i]-[i-1])，最大的元素肯定不能用第二种方案消掉，即用第三种方案，也许是的

by 晴空一鹤 @ 2022-10-15 12:42:18

楼上正解

by DolorisX @ 2022-10-15 13:09:35

@Reimu_Hakurei hack：

a=\{2,3,3,114513\}

你的答案：114515

实际答案：114514

by Kreado @ 2022-10-15 13:36:04

那就不去重，做链表处理

by Kreado @ 2022-10-15 13:36:55

@xieyikai2333

|