題目連結:
題目大意:
第一列給定三整數 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 的函數值比較大小。最大的即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。