codeforces：C. 1D Sokoban【二分专练 + 灵光一现】

分析

推箱子问题，问能够让多少个箱子推到特殊位置，从0开始推
那么我们有一个很贪心的思路：把连续箱子中的最右的位置放到特殊位置上，这样可以对于每个特殊位置的左边覆盖最多的位置
这样的话我们需要二分，记录左边连续的箱子数，和原本same的个数
左边连续的箱子特殊位置数两次二分：
1.找到连续的个数
2.找到左边界的idx
3.计算在这连续区间中的特殊位置个数即可

Ac code

import sys
from collections import defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readlinedef solve():n, m = list(map(int, input().split()))a = list(map(int, input().split()))b = list(map(int, input().split()))# start at 0; < 0; > 0# x x + 1 x + 2...# two partsx1, y1 = bisect_left(a, 0), bisect_left(b, 0)# 核心思路：把连续箱子中的最右的位置放到特殊位置上，这样可以对于每个特殊位置的左边覆盖最多的位置ans = 0def get_max_num(a, b):mp = defaultdict(int)for v in a:mp[v] = 1# original samesame = 0for v in b:if mp[v] == 1:same += 1maxn = samefor i, v in enumerate(b):# delete 1# if v in mp => Olognif mp[v] == 1: # O1same -= 1# core# how many concutive(including same)idx1 = bisect_right(a, v)# how many special(most left: v - idx1 + 1, most right:v)idx2 = bisect_left(b, v - idx1 + 1)maxn = max(maxn, same + i - idx2 + 1)return maxnans += get_max_num(a[x1:], b[y1:])new_a = [-aa for aa in a[:x1]]new_b = [-bb for bb in b[:y1]]ans += get_max_num(new_a[::-1], new_b[::-1])print(ans)if __name__ == '__main__':for _ in range(int(input())):solve()

总结

需要注意一个很细的细节
if v in mp => O(logn)
if mp[v] == 1 -> O(1)
谨慎！