[BianSearch]Boj 7795:食べるか食べるか

1440 ワード
テキストリンク

[BianSearch]Boj 7795:食べるか食べるか


Link: https://www.acmicpc.net/problem/7795

質問する


深海には二つの生命体AとBが存在する.AはBを食べる.Aさんは自分より小さい食べ物しか食べられません.例えば、Aの大きさが{8,1,7,3,1}であり、Bの大きさが{3,6,1}であれば、AがBを食べることができるペアは7種類ある.8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

2つの生命体AとBの大きさが与えられた場合、Aの大きさがBより大きいかどうかを決定するプログラムを作成します.

入力


第1行は、試験例の個数Tを与える.各テストケースの最初の行は、Aの数NおよびBの数Mを与える.2行目はAのすべてのサイズを与え、3行目はBのすべてのサイズを与える.サイズは正の整数です.(1 ≤ N, M ≤ 20,000)

しゅつりょく


各テストボックスは、1対のAがBより大きい数を出力する.

質問へのアクセス


Aリストの数はBリストの中の大数の問題なので、一つずつ求めるとNxN演算が行われます.したがって、タイムアウトの問題が発生する可能性があるため、二分検索で演算する必要があります.二分ルックアップを使用して演算する場合は、Nxlog(M)と同じ時間が必要です.

Code | Python

import sys
si = sys.stdin.readline
T = int(si())

def BS(list_,L,R,X):
	result = L-1
	while L <= R:
		M = (L+R)//2
		if list_[M] < X:
			result = M
			L = M+1
		else:
			R = M-1
	return result

def runTest():
	Asize,Bsize = map(int,si().split())
	A = list(map(int,si().split()))
	B = list(map(int,si().split()))
	B.sort()

	answer = 0
	for x in A:
		answer += BS(B,0,Bsize-1,x) + 1
	print(answer)

for _ in range(T):
	runTest()

Screenshot


JavaSE国際化の簡単な例
ファイルアップロード機能を実現し、アップロードした画像をページに表示する