面試官在美國，因此約的時間只能是早上八點到九點萨西。一晚上沒睡好。
面試官是我面過的覺得最好的了键耕，在我不會的時候可以耐心等我想一下寄狼，我說實在不會的會給我一點提示丁寄，讓我再想，無奈我太菜了泊愧。
自我介紹
講講項目
題目一
給出指定精度的double類型開方
寫了個二分伊磺，但是0的時候忘了判，在面試官提示下加了個特判删咱。
題目二
一條直線上有n個包裹屑埋，給出包裹的坐標(biāo)，現(xiàn)在要修建一個倉庫痰滋，使得所有包裹到倉庫的花費之和最小雀彼，花費定義為包裹到倉庫的距離的平方壤蚜，問倉庫的位置。
一開始我說是中位數(shù)徊哑，后來面試官用試探的語氣說確定嗎袜刷，我又說是平均數(shù)，然后在草稿上算了下莺丑，面試官不等我算完直接說現(xiàn)在告訴你是平均數(shù)著蟹，你可以證明一下嗎。
然后我就開始證明：
假設(shè)位置為x[]梢莽，倉庫的位置為avg萧豆，距離總和為sum。
cost = (x[0] - avg)^2 + (x[1] - avg)^2 + ... + (x[n-1] - avg)^2
= (x[0]^2 + x[1]^2 + ... + x[n-1]^2) - 2 * (x[0] + x[1] + ... + x[n-1]) * avg + n * avg^2
= c(常數(shù)) - 2 * b(常數(shù)) * avg + a(常數(shù)) * avg^2
極值 = (-b) / (2*a) = 2 * sum / (2 * n) = sum / n = 平均數(shù)
題目三
第三題就是將第二題的一個倉庫改為m個倉庫的時候的最小花費昏名。
面試官一開始提示用dp涮雷，然后再給我定義了一個狀態(tài)，就差把遞推式告訴我了轻局，我還是不會洪鸭。面試官表示絕望，說時間不多了仑扑，我們先這樣吧览爵。
后面自己寫了一遍。
具體思路可以看 我的博客鏈接镇饮。
#include <bits/stdc++.h>
using namespace std;
const int N = 211;
const int INF = 0x3f3f3f3f;
int n, m, x[N];
double dp[N][N], cost[N][N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
double sum = 0;
for (int k = i; k <= j; k++)
sum += x[k];
sum /= (j - i + 1);
cost[i][j] = 0;
for (int k = i; k <= j; k++)
cost[i][j] += (x[k] - sum) * (x[k] - sum);
}
}
// 定義狀態(tài)dp[i][j]為前i個包裹用j個倉庫的最小花費
for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) dp[i][j] = 1e9;
dp[0][0] = 0;
for (int i = 1; i <= n; i++) { // 枚舉當(dāng)前要放多少個包裹
for (int j = 1; j <= i && j <= m; j++) { // 枚舉倉庫蜓竹，要求倉庫的數(shù)量比包裹數(shù)量少
for (int k = j; k <= i; k++) {
// 枚舉從第k個包裹到第i個包裹全都放到最后一個倉庫，
// 而且滿足前面的j-1個倉庫都至少一個包裹
dp[i][j] = min(dp[i][j], dp[k-1][j-1] + cost[k][i]);
}
}
}
printf("%.2f\n", dp[n][m]);
return 0;
}
/*
6 3
1 3 7 9 10 16
5 3
1 3 7 9 10
1 1
5
*/
總結(jié)
相對擅長的算法被碾壓了储藐，表示受到打擊俱济。在準(zhǔn)備其他的過程中，還是得保持刷題的手感钙勃。
