面试官在美国，因此约的时间只能是早上八点到九点。一晚上没睡好。
面试官是我面过的觉得最好的了，在我不会的时候可以耐心等我想一下，我说实在不会的会给我一点提示，让我再想，无奈我太菜了。
自我介绍
讲讲项目
题目一
给出指定精度的double类型开方
写了个二分，但是0的时候忘了判，在面试官提示下加了个特判。
题目二
一条直线上有n个包裹，给出包裹的坐标，现在要修建一个仓库，使得所有包裹到仓库的花费之和最小，花费定义为包裹到仓库的距离的平方，问仓库的位置。
一开始我说是中位数，后来面试官用试探的语气说确定吗，我又说是平均数，然后在草稿上算了下，面试官不等我算完直接说现在告诉你是平均数，你可以证明一下吗。
然后我就开始证明：
假设位置为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(常数) - 2 * b(常数) * avg + a(常数) * avg^2
极值 = (-b) / (2*a) = 2 * sum / (2 * n) = sum / n = 平均数
题目三
第三题就是将第二题的一个仓库改为m个仓库的时候的最小花费。
面试官一开始提示用dp，然后再给我定义了一个状态，就差把递推式告诉我了，我还是不会。面试官表示绝望，说时间不多了，我们先这样吧。
后面自己写了一遍。
具体思路可以看 我的博客链接。
#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);
}
}
// 定义状态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++) { // 枚举当前要放多少个包裹
for (int j = 1; j <= i && j <= m; j++) { // 枚举仓库，要求仓库的数量比包裹数量少
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
*/
总结
相对擅长的算法被碾压了，表示受到打击。在准备其他的过程中，还是得保持刷题的手感。
