初夏的雨 山东大学·2022届

APP 内打开

滴滴笔试题参考解题报告

连续最大和

分析:

经典水题。没啥好说的. 时间复杂度: O(n)

参考code:

#include

using namespace std;

int main(){

int n;

scanf("%d",&n);

int sum = 0, mx = -99999999;

for(int j = 0; j < n; j++){

int temp;

scanf("%d",&temp);

if(sum < 0) sum = temp;

else sum += temp;

mx = max(sum, mx);

}

printf("%d\n",mx);

}

餐馆

分析:

贪心。先把顾客进行消费金额降序,人数升序排序。然后枚举每波顾客去二分当前最适合的

桌子的容量，维护答案即可,注意答案可能爆int。这题裸暴力过不了。不能拆桌。时间复杂度：O(mlogm + nlogm)

参考code:

#include

using namespace std;

struct node{

int b,c;

};

int cmp(node x,node y){

if (x.c == y.c) {

return x.b < y.b;

}

return x.c > y.c;

}

int n,m;

long long ans;

std::vector v;

std::multimap mp;

int main(){

scanf("%d%d",&n,&m);

for(int i = 0; i < n; i++){

int x; scanf("%d",&x);

mp.insert(std::pair(x, 1));

}

for(int i = 0; i < m; i++){

int x, y;

scanf("%d%d",&x,&y);

node tmp;

tmp.b = x, tmp.c = y;

v.push_back(tmp);

}

sort(v.begin(),v.end(),cmp);

for(int i = 0; i < m; i++){

std::map::iterator it = mp.lower_bound(v[i].b);

if (it != mp.end()) {

mp.erase(it);

ans += v[i].c;

}

printf("%lld\n",ans);

}

发布时间：2020年07月18日

上一个下一个

我来说两句…

共 20 条评论

说好的星球还去吗🌍 北京邮电大学·2022届 30

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

2020年10月17日回复

幸运的小金Angel 江西财经大学·2022届 28

问答题参考解法：题目大意：给你一个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)

2020年10月17日回复

占有欲_ 上海财经大学·2022届 28

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

2020年10月16日回复

苏大泽ㄣ 东北林业大学·2022届 27

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

2020年10月16日回复

丿爱你不变心彡 华南师范大学·2022届 25

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

2020年10月17日回复

韦丽丽 山东财经大学·2022届 23

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

2020年10月17日回复

成功路上总施工ing 四川师范大学·2022届 22

求大神看看，为什么超内存提示！！！！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 ; }

2020年10月17日回复

妄我深拥 兰州大学·2022届 22

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

2020年10月16日回复

冰糖葫芦娃 哥伦比亚大学·2022届 22

// // 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 ; }

2020年10月16日回复

成熟最迷人 山东科技大学·2022届 21

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

2020年10月17日回复

沐雨白 西南财经大学·2022届 18

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

2020年10月17日回复

摩羯S 香港城市大学·2022届 12

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

2020年10月17日回复

SgtRL-3 东南大学·2022届 11

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

2020年10月17日回复

六六哥伦比亚大学·2022届 10

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

2020年10月16日回复

北纬°不眠的思念 复旦大学·2022届 9

复制代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 //与楼主两点不同： 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; }

2020年10月16日回复