f638. 支點切割
Tags :
Accepted rate : 359人/488人 ( 74% ) [非即時]
評分方式:
Strictly

最近更新 : 2023-08-17 12:53

Content

輸入一個大小為 𝑁 的一維整數陣列 p[] ,要找其中一個所謂的最佳切點將陣列切成左右兩塊,然後針對左右兩個子陣列繼續切割,切割的終止條件有兩個:子陣列範圍小於 3 或切到給定的層級 𝐾 就不再切割。而所謂最佳切點的要求是讓左右各點數字與到切點距離的乘積總和差異盡可能的小,但不可以是兩端點,也就是說,若區段的範圍是[𝑠, 𝑡],則要找出切點 𝑚 ∈ [𝑠+1, 𝑡-1],使得  越小越好,如果有兩個最佳切點,則選擇編號較小的。所謂切割層級的限制,第一次切以第一層計算。

Input

輸入格式:第 一行 有兩 個正整數 𝑁 與 𝐾 。 第二行 有 𝑁 個正整數 代表陣列內容 p[1] ~ p [𝑁],數字間以空白隔開, 總和不超過 109。 𝑁 ≤ 50000,切割層級限制 𝐾 < 30。

Output

所有切點的 p[ ] 值總和。

Sample Input #1
7 1
2 4 1 3 7 6 9
Sample Output #1
7
Sample Input #2
7 3
2 4 1 3 7 6 9
Sample Output #2
11
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
Hint :
Tags:
出處:
APCS201802程式實作題3 [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
35086 willy633526@ ... (ByTech) f638
python 題解
483 2023-05-08 10:38
30025 Williecraft (張哲維) f638
找支點O(1)的方法
1768 2022-04-21 21:12
28248 r1cky (hehe) f638
Java 解題心得
788 2021-11-20 23:09
24182 hshua (hshua) f638
遞迴分治
2377 2021-01-25 22:17