阿里 笔试 2021

不确定对不对，但测试结果是正确的

不知道这样能做出多少

笔试时写的O(n2)，过70%，笔试后想到的O(nlongn),（这里假设冲突对不会重复） #include<iostream> #include<algorithm> #include<vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> a(n), b(n); vector<int> del(n); int sup = 0; for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; sup += b[i]; del[i] = b[i] - a[i]; } vector<int> ans(n, sup); for (int i = 0; i < n; ++i) ans[i] += n * b[i]; sort(del.begin(), del.end()); vector<int> sum(n + 1, 0); for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + del[i]; for (int i = 0; i < n; ++i) { int curDel = b[i] - a[i]; int idx =  upper_bound(del.begin(), del.end(), curDel)- del.begin(); ans[i] -= sum[n] - sum[idx]; ans[i] -= idx * curDel; ans[i] -= b[i] + a[i]; } for (int i = 0; i < m; ++i) { int l, r; cin >> l >> r; --l; --r; int curDel = min(a[l] + b[r], a[r] + b[l]); ans[l] -= curDel; ans[r] -= curDel; } for (int i = 0; i < n; ++i) cout << ans[i] << " "; return 0; }

我调试系统出问题了，一调试就卡着不动，一直在加载，好烦也不知道写的对不对

阿里的内推老师说笔试不过的话要加一轮笔试 有没有大佬知道加试是怎么样的形式啊？题目难度如何？

好长

盲猜一波是背包问题，用动规

（考后思考） 直接暴力枚举，没什么优化的空间 对于每一个零件，都需要枚举其与剩下的零件组合后的不稳定值，且时空不能同时选，所以只需要枚举2次。 比如对零件一，组合如下 （1,2）：3（=-1+4）或5（=3+2）；选最小稳定值（1,2）=3 同理有（1,3）=0，（1,4）=不可组合=0，（1,5）=1 最后，零件1为 3+0+0+1 = 4 那么，零件二而言，组合应该是（2,1），（2,3），（2,4），（2,5），只有（2,1）计算过，其他都没算过。。所以只能暴力枚举。。开一个很大的二维矩阵挨个算就完了。时间复杂度O(n2)，空间复杂度O（n2） 要么每次都重新计算一遍，时间复杂度O(n2)，空间复杂度O（n）

O(N+M+NlogN+MlogM)算法

自己运行例子可以运行，怎么一提交就超时啊

笔试多少分能过啊

 这题把算法写出来就自动交卷了，也不知道写的对不对

连续两次阿里笔试0分了 （这次是1分😂）感觉自己的智商受到了侮辱

看到这么长的题目就给跪了