城堡OA这是换题了？

感觉第二题常规dp可解 第一题binary search貌似可行

binary search 的解法

1. 
   
2. int findMaximum(vector<int>& a, int m) {
   
3.   // see if we can find a solution that has minimum >= x.
   
4.   auto check = [&](int x) {
   
5.     int j = 0; // current
   
6.     for (int i = 0; i < m - 1; i ++) {
   
7.       // a[k] >= x + a[j]
   
8.       auto it = lower_bound(a.begin() + j + 1, a.end(), a[j] + x);
   
9.       if (it == a.end())
   
10.         return false;
    
11.       j = it - a.begin();
    
12.     }
    
13. 
    
14.     return true;
    
15.   };
    
16. 
    
17.   int bst = 0;
    
18.   int lo = 0, hi = 1e9 + 1;
    
19.   while (lo <= hi) {
    
20.     int mi = lo + (hi - lo) / 2;
    
21.     if (check(mi)) {
    
22.       bst = mi;
    
23.       lo = mi + 1;
    
24.     } else {
    
25.       hi = mi - 1;
    
26.     }
    
27.   }
    
28. 
    
29.   return bst;
    
30. }

复制代码

第二题：

1. 
   
2. long maxInversions(vector<int> &a) {
   
3.   int n = a.size();
   
4.   vector<long> dp(n, 0);
   
5. 
   
6.   for (int i = n - 1; i >= 0; -- i)
   
7.     for (int j = i + 1; j < n; ++ j)
   
8.       if (a[i] > a[j]) dp[i] ++;
   
9. 
   
10.   long ans = 0;
    
11.   for (int i = n - 1; i >= 0; -- i)
    
12.     for (int j = i + 1; j < n; ++ j)
    
13.       if (a[i] > a[j]) ans += dp[j];
    
14. 
    
15.   return ans;
    
16. }

复制代码

[/i][/i][/i]
[i][i]时间复杂度 O(N^2)，对给定数据量（5000）应该不会超时。[/i][/i]

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第二题感觉N^2是可以过的？
循环一遍给每个数记录一下这个数后面有多少个比自己小的数
然后循环i,j分别当前两个数，j后面有多少个比自己小的，就是可以有多少组解，最后加起来就行了