發表新討論
#30178: O(n)


fire5386 (becaidorz)

i164. 比對卡片(進階版) -- TOI 練習賽 202204 新手組 | From: [114.25.105.16] | 發表日期: 2022-05-05 19:00

int prev[100005] 紀錄各個數字前一次出現的index

從左邊和右邊各掃過取min就是答案了

時間複雜度：O(n)

#30181: Re: O(n)


linlincaleb@gmail.com (臨末之頌)

i164. 比對卡片(進階版) -- TOI 練習賽 202204 新手組 | From: [111.248.101.95] | 發表日期: 2022-05-05 20:26

int prev[100005] 紀錄各個數字前一次出現的index

從左邊和右邊各掃過取min就是答案了

時間複雜度：O(n)

是下面的陣列還是上面的阿 看不太懂 怎麼找index阿 不是還要用lower_bound嗎

#30183: Re: O(n)


fire5386 (becaidorz)

i164. 比對卡片(進階版) -- TOI 練習賽 202204 新手組 | From: [114.25.105.16] | 發表日期: 2022-05-05 21:02 
for(int i = 0; i < n; ++i) {
	prev[b[i]] = i;
	if(prev[a[i]] != -1) {
		ans[i] = min(ans[i], abs(i - prev[a[i]]));
	}
}

不需要用到lower_bound找位置 這樣複雜度少一個log(n)

#30184: Re: O(n)


linlincaleb@gmail.com (臨末之頌)

i164. 比對卡片(進階版) -- TOI 練習賽 202204 新手組 | From: [111.248.101.95] | 發表日期: 2022-05-05 21:30 
for(int i = 0; i < n; ++i) {
	prev[b[i]] = i;
	if(prev[a[i]] != -1) {
		ans[i] = min(ans[i], abs(i - prev[a[i]]));
	}
}

不需要用到lower_bound找位置 這樣複雜度少一個log(n)

哦 受教了 感謝大大分享

ZeroJudge Forum