求助一道OA题目

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

SoWhat0309 发表于 2022-12-16 11:34
购买数量不限的情况就是0-1背包，O(n logn) sort的也算贪心……而且会被一些奇奇怪怪的数据卡掉

按hap ...

目前我能想到最好的就是排序后双指针，其他的都最大是n^2，包括traversal

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

SoWhat0309 发表于 2022-12-16 11:50
再看了下x和y的范围，感觉开个堆/TreeMap去traverse， O(n log(heap size））也离O(n)远得很。不过10的5 ...

应该是这样的，感觉原帖里面说可以O(n)的是没考虑只在一个商店里买的情况

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

请问这道题是这周的tiktok的oa吗？

匿名用户 发表于 2022-12-16 12:18
请问这道题是这周的tiktok的oa吗？

不知道哎，应该不是吧

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第一步按价格倒序排序，O(n log n)。不排序不可能。
第二步分成两个商店各买一个，商店之一买两个，共三种情况，取最优解。
对于两个商店各买一个的情况，直接分别找没超过对应礼品卡上限的最大快乐值即可，O(N).
对于商店之一买两个的情况，单调栈从左往右，栈内部的单调性是价格递减，快乐递减。复杂度 O(N).
或者用二分也无妨，复杂度 O(n log n)