Quora OA 跪经 Changing Managers

题目名字叫Changing Managers

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

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

件。
哪个大神能给个解法？

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. struct BIT{
   
5.     vector<int> a;
   
6.     int total;
   
7.     BIT(int n): a(n+2,0),  total(0){}
   
8.     void add(int k) {
   
9.         int p1 = k + 1;
   
10.         while(p1 < a.size()) {
    
11.             a[p1] += 1;
    
12.             p1 += (p1 & -p1);
    
13.         }
    
14.         total += 1;
    
15.     }
    
16.     int query(int k) {
    
17.         // larger than k
    
18.         k += 1;
    
19.         int val = 0;
    
20.         while(k > 0) {
    
21.             val += a[k];
    
22.             k -= (k & -k);
    
23.         }
    
24.         return total - val;
    
25.     }
    
26. };
    
27. 
    
28. vector<int> bruteforce(vector<pair<int,  pair<int,  int> > > & data){
    
29.     vector<int> res;
    
30.     for(int i=0; i<data.size(); ++i) {
    
31.         int c = 0;
    
32.         for(int j=0; j<data.size(); ++j) {
    
33.             if (i != j && data[j].first > data[i].first && data[j].second.first > data[i].second.first) c += 1;
    
34.         }
    
35.         res.push_back(c);
    
36.     }
    
37.     return res;
    
38. }
    
39. 
    
40. int main () {
    
41.     int n; cin >> n;
    
42.     vector<pair<int,  pair<int,  int> > > data;
    
43.     int id = 0;
    
44.     while(n --) {
    
45.         int l1, l2;
    
46.         cin >> l1 >> l2;
    
47.         data.push_back({l1,  {l2,  id++}});
    
48.     }
    
49.     // auto bf_res = bruteforce(data);
    
50. 
    
51.     sort(data.begin(),  data.end());
    
52. 
    
53.     vector<int> res(data.size(),  0);
    
54.     BIT bit(1000000);
    
55.     for(int i=(int)data.size() - 1; i>=0; --i) {
    
56.         int p1 = i;
    
57.         while(p1 >= 0 && data[p1].first == data[i].first) --p1;
    
58.         for(int j=p1+1; j<=i; ++j) {
    
59.             int id = data[j].second.second;
    
60.             int l2 = data[j].second.first;
    
61.             res[id] = bit.query(l2);
    
62.         }
    
63.         for(int j=p1+1; j<=i; ++j) {
    
64.             bit.add(data[j].second.first);
    
65.         }
    
66.         i = p1 + 1;
    
67.     }
    
68.     // cout << (bf_res  == res) << endl;
    
69. }
    

复制代码

橙小夕 发表于 2017-9-21 05:16
感觉就是俄罗斯套娃的解法，稍微变一下形，一个维度排序加BST搜另一个维度。(NlogN）复杂度

这个最后需要output 每个人最多能有几个mentor。感觉套娃解法不能解出来

naive的解法是O(N2), 需要做到O(NlogN)

楼主，我不是很懂N <= 5000的占50%是什么意思，N不应该是输入的amount吗？另外，L and E unique的占70%， 是指分别占70%还是两个合起来一起看占70% ?

小雨嘀嗒 发表于 2016-12-4 06:52
楼主，我不是很懂N

我的理解，它是在说明它提供的test集数据分布情况，可能要利用数据的这些特性，然而我并没有想出来。。。

yuyahome 发表于 2016-12-4 08:40
我的理解，它是在说明它提供的test集数据分布情况，可能要利用数据的这些特性，然而我并没有想出来。。。

我也没想出来。。。

小雨嘀嗒 发表于 2016-12-5 12:05
我也没想出来。。。

似乎和leetcode上的俄罗斯套娃题很像，你去看看。

竟然现在也收到一模一样的题，请问楼主现在知道如何解了吗？

谢谢楼主贡献题目！

为什么我这里 您所在的用户组无法下载或查看附件