问题遇到的现象和发生背景
测试共30步,每步有时间和内存限制
时间限制: 5 s
内存限制: 256 MB
彼佳来到异国他乡,决定买一件纪念品。在纪念品商店里,各种类型的小雕像排成一排,一个小雕像成本正好是它单位的当地货币。彼佳决定购买从1到X的各种小雕像。事实证明,如果彼佳购买的小雕像不在任意位置,而是在某个连续的部分(包括从 1 到 X的某个位置的所有小雕像),他将获得不错的折扣。彼佳立刻意识到他可能需要买几个相同类型的小雕像,他决定回家后多给朋友们赠送。例如,如果商店里的小雕像按照1 2 2 3 3 1的顺序展示,并且彼佳想购买 1到3 类型的小雕像,然后他可以购买第一个到第四个位置的小雕像(将购买两个2类型的小雕像)。如果小雕像 1 2 5 4 3 陈列在商店中,那么彼佳将购买所有 5 个小雕像。帮助彼佳确定商店中排列的小雕像的最低总成本,以便其中他们有从1到k的各种小雕像。保证所有测试数据都存在答案。输入第一行包含两个整数n和k(1<k<n<500,000。第二行包含n个整数(小雕像的类型i,1<a_i<n),纪念品商店小雕像的描述。小雕像从左到右列出。保证所有测试数据都存在答案。输出打印一个整数,即他可以购买小雕像的最小本地货币数量(不包括未来的折扣)。
标准输入
6 3(下一列有6个元素,他想用折扣价买123)
1 2 2 3 3 1(他最终买了1223,花费为和1223的和 8)
标准输出
8
标准输入
5 3
1 2 5 4 3 (他会全部都买)
标准输出
15
标准输入
6 3
1 2 6 3 3 1
标准输出
12
标准输入
6 1
6 2 3 1 2 3
标准输出
1
标准输入
7 7
1 2 3 4 6 5 7
标准输出
28
标准输入
10 2
1 9 2 4 3 1 8 2 10 9
标准输出
10(他会买2431)
python求解答,怎么实现这个问题?
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
3条回答 默认 最新
- 索利亚噶通 2021-12-15 15:49关注
你给的用例全部能测试通过, 有用请采纳, 没用再讨论
""" 题解: 输入n, k n: 雕像的个数 k: 保证必须购买[1, k] 所有编号的雕像 双指针 + hash表 """ n, k = list(map(int, input().split())) nums = list(map(int,input().split())) minCost = float("INF") i, j = 0, -1 # 双指针 numSet = {} # 用于查看[i, j]之间是否已经存在某个数 sumTemp = 0 # 暂时存放[i, j]之间的价格之和 while i < n: if len(numSet) == k: if sumTemp < minCost: minCost = sumTemp sumTemp -= nums[i] if nums[i] in numSet.keys(): numSet[nums[i]] -= 1 if numSet[nums[i]] == 0: del numSet[nums[i]] i += 1 # 左指针右移 else: if j + 1 < n: j += 1 sumTemp += nums[j] if nums[j] <= k: if nums[j] in numSet.keys(): numSet[nums[j]] += 1 else: numSet[nums[j]] = 1 else: # 右指针到头 break print(minCost)
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 1无用
悬赏问题
- ¥15 msix packaging tool打包问题
- ¥28 微信小程序开发页面布局没问题,真机调试的时候页面布局就乱了
- ¥15 python的qt5界面
- ¥15 无线电能传输系统MATLAB仿真问题
- ¥50 如何用脚本实现输入法的热键设置
- ¥20 我想使用一些网络协议或者部分协议也行,主要想实现类似于traceroute的一定步长内的路由拓扑功能
- ¥30 深度学习,前后端连接
- ¥15 孟德尔随机化结果不一致
- ¥15 apm2.8飞控罗盘bad health,加速度计校准失败
- ¥15 求解O-S方程的特征值问题给出边界层布拉休斯平行流的中性曲线