[0906]滴滴笔试题参考解题报告

问答题参考解法： 题目大意：给你一个ipv4地域库（ipv4地址的网段表示法，比如12.34.56.0/24，对应相应地理位置的表），保证各个网段互不重叠，但是一个地域可以对应多个网段。请设计一个数据结构，能过快速地查询用户询问的ip所对应的地理位置。请说明你的方法的时空复杂度。 参考解法： 计算机中ipv4地址是32位无符号整数。 我们将ipv4的地址和网段都变成32位无符号整数，然后转换成对应的32位的二进制表示。 之后使用字典树/键树/Trie（二叉树也可以），每个节点有2个分支：一个分支表示下一位是0，另一个分支表示下一位是1. 首先要将所有地域库的信息插入这个树中。对网段，保留相应的掩码长度，在掩码长度最后一位对应的节点，顺带标记上，这是一个网段节点，对应的地域为xxx。 插入完成之后，我们可以处理查询。对每个查询，转成32位的01串，在树上，根据每一位的具体值，决定往下走到哪个节点，来进行查找。当走到某个节点，走不下去的时候： 如果这个节点没有地域信息，说明库中没有对应条目。 如果这个节点有地域信息，说明我们找到了，返回这个地域信息。 综上所述： 插入阶段： 时间复杂度O(32n)=O(n) 空间复杂度O(32n)=O(n) 其中n为地址库中的地址数目 查询阶段： 时间复杂度O(32)=O(1) 空间复杂度O(1)

呃呃呃额额呃呃呃，我要是改成%lld说不定就100%AC了 。楼主不是 %lld前是不是过了50%?

//与楼主两点不同： 1.multimap改为multiset //2.存储就餐人数、消费额时用vector，v[0]是消费额，v[1]是消费人数 //之所以消费额放前面就是为了排序时以消费额为准，这样不再需要自定义结构体和比较函数 //昨晚没想起来用multiset，更没想起来用其成员函数lower_bound，只是从头到尾搜索，也没用long long，结果50% #include<iostream> #include<vector> #include<algorithm> #include<set> using namespace std; int main() { int n , m, x, y; cin >> n >> m; multiset<int> table; for(int i = 0; i < n; ++i) { cin >> x; table.insert(x); } vector<vector<int> > guest; for(int i = 0; i < m; ++i) { cin >> x >> y; guest.push_back({y, x}); //x:人数 y:消费额，y放vector的前面，排序时以消费额为准 } sort(guest.begin(),guest.end(), greater<vector<int> >()); long long maxValue = 0; for(int i = 0; i < m && !table.empty(); ++i) { auto it = table.lower_bound(guest[i][1]); //guest[i][1]就餐人数 if(it != table.end()) { maxValue += guest[i][0]; //guest[i][0]消费额 table.erase(it); } } cout << maxValue <<endl; return 0; }

第二题可以用C++ STL中的优先队列来做，有人和我一样的思路吗？

想问一下第二题桌子可以用multiset存储吗

好像没有考虑int越界 过了50%。。

http://www.cnblogs.com/CCBB/archive/2009/04/25/1443455.html  第一题可以参考下这个blog

求告知题目详细是啥，还有那个简单题具体怎么问的，题没看清都没时间了

// //  main.cpp //  DiDitest001 // //  Created by Rouen on 16/9/6. //  Copyright © 2016 年 Rouen. All rights reserved. // #include <iostream> #include <vector> #include <queue> #include <stack> #include <map> #include <algorithm> using namespace std ; class comppair{ public :     int operator ()( pair < int , int > a, pair < int , int > b) {         if (a. second != b. second )             return a. second > b. second ;         else             return a. first > b. first ;     } }; long long helper( int n, int m, multiset < int >& arr, vector < pair < int , int >> &cost) {     long long res = 0 ;     int resid = m;     sort (cost. begin (),cost. end (), comppair ());     for ( int k = 0 ;k <=m;++k) {         auto ii = arr. lower_bound (cost[ k ]. first );         if (ii != arr. end ()) {             res += cost[ k ]. second ;             arr. erase (ii);             --resid;         }         if (resid == 0 ) break ;     }          return res; } int main( int argc, const char * argv[]) {     // insert code here...     //std::cout << "Hello, World!\n";     int n,m;     multiset < int > arr;     vector < pair < int , int >> cost;     int tmp1, tmp2,tmp3;     while ( cin >> n >> m) {         arr. clear ();         cost. resize (m);         for ( int i = 0 ;i < n;++i) {             scanf ( "%d" ,&tmp3);             arr. insert (tmp3);         }         for ( int i = 0 ;i < m;++i) {             scanf ( "%d" ,&tmp1);             scanf ( "%d" ,&tmp2);             //scanf("%d %d",&tmp1,&tmp2);             cost[ i ] = {tmp1,tmp2};         }         printf ( "%lld\n" , helper (n, m, arr, cost));     }     return 0 ; }

忘记set容器里有lower_bound功能了。。。不过数据挺水，我暴力加普通二分优化也过了。。

结果int类型有过的没？

然后我想问 LZ这样的代码能AC么？还是事后自己做的？

求大神看看，为什么超内存提示！！！！cout<<20<<endl交上去测试了下能通过一个case啊！！！ #include "iostream" #include "string" #include "cstdio" #include "cstring" #include "map" #include "algorithm" using namespace std; struct customer {     int count;     int money; }; customer cus[ 50000 ]; int cmp(customer a,customer b) {     return a.money>b.money; } int main() {     int n,m;     while (cin>>n>>m)     {         memset(cus, 0 , sizeof (cus));         map< int , int > table;         int mx= 0 ;         for ( int i= 0 ;i<n;++i)         {             int a;             cin>>a;             if (mx<a) mx=a;             table[a]++;         }                           for ( int i= 0 ;i<m;++i)             cin>>cus[i].count>>cus[i].money;                           long long int res= 0 ;         sort(cus,cus+m,cmp);         for ( int i= 0 ;i<m;++i)         {             for ( int k=cus[i].count;k<=mx;++k)             {                 if (table[k]> 0 )                 {                     res+=cus[i].money;                     table[k]--;                     break ;                 }             }         }                  cout<<res<<endl;     }     return 0 ; }

感觉思路差不多 一直tle 求看 import java.util.*; public class Main { public static class custom implements Comparable<custom> { int num; int cash; public custom(int a, int b) { num = a; cash = b; } @Override public int compareTo(custom o) { return o.cash - this.cash; } } public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); int m = s.nextInt(); int[] table = new int[n]; for (int i = 0; i < n; i++) { table[i] = s.nextInt(); } Arrays.sort(table); TreeMap<Integer, Queue<custom>> mmm = new TreeMap<>(); custom[] c = new custom[m]; for (int i = 0; i < m; i++) { c[i] = new custom(s.nextInt(), s.nextInt()); if (!mmm.containsKey(c[i].num)) { mmm.put(c[i].num, new PriorityQueue<>()); } mmm.get(c[i].num).add(c[i]); } long ans = 0; for (int i = 0; i < n; i++) { int max = 0; int index = -1; Map<Integer, Queue<custom>> tmpmap = mmm.subMap(0, table[i] + 1); Iterator<Map.Entry<Integer, Queue<custom>>> it = tmpmap.entrySet().iterator(); while (it.hasNext()) { Map.Entry<Integer, Queue<custom>> e = it.next(); if (e.getValue().peek().cash > max) { max = e.getValue().peek().cash; index = e.getKey(); } } ans += max; if (index != -1) { mmm.get(index).poll(); if (mmm.get(index).isEmpty()) { mmm.remove(index); } } } System.out.println(ans); } }

没审清题。。。做法和你的基本一样，但是我以为一组人可以坐多个桌子，结果写崩了。。。泪奔

STL用的好6，没考虑二分和int只过了20%

调了半个小时，发现错在写了while()处理多个用例 我了个去

为了考虑结果超出int，用long型存储，结果直接超时，出题人也是。。。，唉，楼主的STL用的好六，厉害！！

只能说滴滴家的餐厅可真够大的，可以容纳2^31个人去吃饭。 出题人为了边界条件连常识都不考虑吗？？