f638. 支點切割
標籤 :
通過比率 : 489人/653人 ( 75% ) [非即時]
評分方式:
Strictly

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

內容

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

輸入說明

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

輸出說明

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

範例輸入 #1
7 1
2 4 1 3 7 6 9
範例輸出 #1
7
範例輸入 #2
7 3
2 4 1 3 7 6 9
範例輸出 #2
11
測資資訊:
記憶體限制: 64 MB
提示 :
標籤:
出處:
APCS201802程式實作題3 [管理者: snail (蝸牛) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
30025 Williecraft (張哲維) f638
找支點O(1)的方法
2378 2022-04-21 21:12
43110 Chaoray (巧克力內餡貢丸) f638
48 2024-10-17 00:21
35086 willy633526@ ... (ByTech) f638
python 題解
791 2023-05-08 10:38
28248 r1cky (hehe) f638
Java 解題心得
991 2021-11-20 23:09
24182 hshua (hshua) f638
遞迴分治
2752 2021-01-25 22:17