切換
舊版
前往
大廳
主題

ZeroJudge - f312: 1.人力分配 解題心得

Not In My Back Yard | 2020-10-19 00:00:06 | 巴幣 0 | 人氣 797

題目連結:


題目大意:
第一列給定三整數 A1 、 B1 、 C1 ,代表如果一號工廠有 X1 名員工,則收益為 A1 × X1 ^ 2 + B1 × X1 + C1;第二列給定三整數 A2 、 B2 、 C2 ,代表如果二號工廠有 X2 名員工,則收益為 A2 × X2 ^ 2 + B2 × X2 + C2

第三列給定一正整數 n (1 ≦ n ≦ 100),代表著員工總數。現在每個員工都一定要被分配到某個工廠去(代表 n = X1 + X2 且 0 ≦ X1 、 X2)。試問,最大的收益值為何?



範例輸入:
2 -1 3
4 -5 2
2


範例輸出:
11


解題思維:
因為 n 非常地小,而且每個員工都需要到工廠去,沒有任何閒置的人。因此我們可以窮舉 X1(或 X2 ,其中之一即可)的值,然後求出 X2 = n - X1 ,再代到題目給定的算式之中。

上述過程之中,求出的最大收益值即是所求。



不過如果 n 很大時,我們可以將所求的函式寫為
Y(X1) = A1 × X1 ^ 2 + B1 × X1 + C1 + A2 × (n - X1) ^ 2 + B2 × (n - X1) + C2

之後利用微積分求出 Y'(X1) 的一次微分:
2(A1 + A2)X1 + B1 - B2 - 2nA1
求出「0」發生的 X1,其值等於
(2nA1 + B2 - B1) ÷ (2(A1 + A2))

因為可能不為整數,所以要找到離最近的整數(但是其值要在 0 ~ n 的範圍之內)。因為一次微分「0」點只代表著極值的發生位置,沒有表明是哪種極值。所以要跟左端點 X1 = 0 、右端點 X1 = n 的函數值比較大小。最大的即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

胖胖貓
本來的水題,活生生變成一個數學問題...你乾脆出個加強版好了XD
2020-10-19 00:20:58
Not In My Back Yard
因為題目本身太簡單了,而且最近都在寫水題,所以想說加點有內涵的東西XD
2020-10-19 01:31:12

更多創作