求助一道OA题目

倒序浏览 · 2022-12-16 10:09:24

在外面看到一道hackerrank的题目，最优解

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

一家商店选两个，也可以从两家各选一个

匿名用户-I4Z5T *2022-12-16 10:21:44* · 2022-12-16 10:21:44

Amazon跟tiktok的可以取多个，就是最简单的1D dp，k个容量下，最大的happiness和

1. 可以O(2N), Amazon跟 tiktok各走一遍
2. 可以O(N)一次一起走完

补充内容 (2022-12-16 10:21 +8:00):
求米

SoWhat0309 · 2022-12-16 11:34:03

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

南宫狗剩 · 2022-12-16 14:13:09

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

匿名用户-ORGO0 *2022-12-16 10:10:11* · 2022-12-16 10:10:11

以防图片看不到

匿名用户-ORGO0 *2022-12-16 10:10:29* · 2022-12-16 10:10:29

以防图片看不到

匿名用户-ORGO0 *2022-12-16 10:25:13* · 2022-12-16 10:25:13

匿名用户发表于 2022-12-16 10:21
Amazon跟tiktok的可以取多个，就是最简单的1D dp，k个容量下，最大的happiness和

1. 可以O(2N), Amazon ...

但是x和y最大为10的9次方啊，dp用什么做行列呢？

匿名用户-ORGO0 *2022-12-16 10:33:18* · 2022-12-16 10:33:18

补充test case

愉悦不断 · 2022-12-16 10:36:27

就很讨厌TikTok的OA，非要把一个简单的问题加一堆乱七八糟的没用废话。

匿名用户-ORGO0 *2022-12-16 10:38:49* · 2022-12-16 10:38:49

愉悦不断发表于 2022-12-16 10:36
就很讨厌TikTok的OA，非要把一个简单的问题加一堆乱七八糟的没用废话。

这题就很迷惑，原帖里面有人说贪心可以O(n)，但却没人放出来实现，我感觉最快也得nlogn排序一下啊

微信用户_708e13f · 2022-12-16 10:49:21

那么大，所以没法用背包呗？有人有思路吗？应该用什么方法解？

匿名用户-ORGO0 *2022-12-16 10:51:18* · 2022-12-16 10:51:18

微信用户_708e13f 发表于 2022-12-16 10:49
那么大，所以没法用背包呗？有人有思路吗？应该用什么方法解？

原帖有人说可以贪心，但是没给实现，不知道是不是真可以用贪心