สมมติว่าเราได้รับสตริงและจำนวนเต็ม k สตริงซ้ำ k ครั้งและทำเป็นสตริงอื่น งานของเราคือการหาความยาวของสตริงย่อยในสตริงใหม่โดยที่ 2 * (จำนวนศูนย์ในสตริงย่อย) <=3 * (จำนวนหนึ่งในสตริงย่อย)
ดังนั้น หากอินพุตเป็น k =2, input_str ='0101011' เอาต์พุตจะเป็น 14
สตริงมีความยาว 7 ดังนั้นสตริงใหม่ที่สร้างจากสตริงแรกคือ 01010110101011 ในที่นี้จำนวน 0s คือ 6 และจำนวน 1s คือ 8 ดังนั้น 2 * 6 <=3 * 8 สตริงย่อยที่ใหญ่ที่สุดจึงเป็นสตริงทั้งหมดที่มีความยาว 14
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- str_len :=ขนาดของอินพุต_str
- list_a :=รายการขนาดใหม่ (str_len + 1) เริ่มต้นด้วย 0s
- list_b :=รายการขนาดใหม่ (str_len + 1) เริ่มต้นด้วย 0s
- list_b[0] :=คู่ใหม่ที่มี (0, 0)
- สำหรับฉันอยู่ในช่วง 0 ถึง str_len ทำ
- list_a[i + 1] :=list_a[i] - 3 *(1 if input_str[i] เหมือนกับ '1', อย่างอื่น 0) + 2 *(1 if input_str[i] เหมือนกับ '0 ', อย่างอื่น 0)
- list_b[i + 1] :=คู่ใหม่ประกอบด้วย (list_a[i + 1], i + 1)
- เรียงลำดับรายการ list_b
- temp_list :=รายการขนาดใหม่ (str_len + 1) เริ่มต้นด้วย 0s
- temp_list[0] :=list_b[0, 1]
- สำหรับฉันอยู่ในช่วง 0 ถึง str_len ทำ
- temp_list[i + 1] =สูงสุดของ (temp_list[i], list_b[i + 1, 1])
- res :=0
- สำหรับฉันอยู่ในช่วง 0 ถึง str_len ทำ
- tmp :=list_b[0, 0] - list_a[i]
- ถ้า list_a[str_len] <=0 แล้ว
- a :=k - 1
- ถ้า tmp + list_a[str_len] * a> 0 แล้ว
- ติดตามตอนต่อไป
- มิฉะนั้นเมื่อ tmp>
0 แล้ว
- ติดตามตอนต่อไป
- มิฉะนั้น
- a :=ขั้นต่ำ (k - 1, มูลค่าขั้นต่ำของ (-tmp / list_a[str_len])))
- v :=a * list_a[str_len] - list_a[i]
- b :=(ตำแหน่งใน list_b ที่สามารถแทรกคู่ (-v + 1, 0) เพื่อรักษาลำดับการเรียงลำดับ) - 1
- res :=สูงสุดของ (res, temp_list[b] - i + a * str_len)
- ผลตอบแทน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
from bisect import bisect_left def solve(k, input_str): str_len = len(input_str) list_a = [0] * (str_len + 1) list_b = [0] * (str_len + 1) list_b[0] = (0, 0) for i in range(str_len): list_a[i + 1] = list_a[i] - 3 * (input_str[i] == '1') + 2 * (input_str[i] == '0') list_b[i + 1] = (list_a[i + 1], i + 1) list_b.sort() temp_list = [0] * (str_len + 1) temp_list[0] = list_b[0][1] for i in range(str_len): temp_list[i + 1] = max(temp_list[i], list_b[i + 1][1]) res = 0 for i in range(str_len): tmp = list_b[0][0] - list_a[i] if list_a[str_len] <= 0: a = k - 1 if tmp + list_a[str_len] * a > 0: continue elif tmp > 0: continue else: a = min(k - 1, -tmp // list_a[str_len]) v = a * list_a[str_len] - list_a[i] b = bisect_left(list_b, (-v + 1, 0)) - 1 res = max(res, temp_list[b] - i + a * str_len) return res print(solve(2, '0101011'))
อินพุต
2, '0101011'
ผลลัพธ์
14
