多多接金币拼多多技术岗 7月19号笔试 第三题题目内容多多在玩一个横版视角的接金币游戏控制的角色可以向左或者向右移动最大移动速度为111个单位距离/秒地图上总共会出现NNN枚金币第iii枚金币会在TiT_iTi秒时准确掉落在坐标XiX_iXi的位置如果没被接住就会瞬间消失。为了接住金币你必须在TiT_iTi秒时出现在XiX_iXi坐标。此外由于角色捡金币需要短暂的硬直时间如果你接住了金币AAA想要再去接金币BBB两次的时间间隔必须严格大于你在两地之间移动所需的时间即满足公式TB−TA∣XB−XA∣T_B - T_A |X_B - X_A|TB−TA∣XB−XA∣假设游戏开始前你可以在任意位置等待。请问你整场游戏最多能接住多少枚金币注意如果同一时刻坐标XXX有多枚金币同时掉落最多只可以接到一个。输入描述第一行包含一个整数N(1≤N≤105)N(1 \le N \le 10^5)N(1≤N≤105)表示金币的数量。接下来NNN行每行两个整数TiT_iTi和XiX_iXi1≤Ti≤1091 \le T_i \le 10^91≤Ti≤109−109≤Xi≤109-10^9 \le X_i \le 10^9−109≤Xi≤109分别表示金币出现时刻和坐标。输出描述输出一个整数表示你最多能收集到的金币数量。样例1输入5 1 2 5 5 2 3 7 4 6 8输出3说明最优接金币路径之一为提取【金币1】→【金币2】→【金币4】总共333枚。题解思路解题思路:逻辑分析 LIS算法题目限制两个金币先后获取的限制为TB−TA∣XB−XA∣T_B - T_A |X_B - X_A|TB−TA∣XB−XA∣,表达式展开为Ti - Xi Tj - XjTi Xi Tj Xj同时满足上述两个表达式即可进行拾取可以设置u Ti - Xiv Ti Xi现在要求最长二维链(A1,B1),(A2,B2),...,(Ak,Bk)需要同时满足A1A2…AkB1B2…Bk目前问题就转换为LIS问题处理逻辑为要实现求v的严格递增子序列长度需要按照u进行升序u相同情况按照v降序(避免u相同情况).然后使用二分求LIS进行求解即可。代码时间复杂度为O(nlogn)C#includebits/stdc.husingnamespacestd;usinglllonglong;structNode{ll u;// T - Xll v;// T X};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;cinN;vectorNodea(N);// Ti - Tj |Xi - Xj| Ti - Xi Tj - Xj and Ti Xi Tj Xjfor(inti0;iN;i){ll T,X;cinTX;a[i].uT-X;a[i].vTX;}sort(a.begin(),a.end(),[](constNodea,constNodeb){if(a.u!b.u){returna.ub.u;}returna.vb.v;});// 求v的严格递增子序列长度 lis[i]代表长度为i的可取最小值vectorlllis;for(autop:a){ll xp.v;autoitlower_bound(lis.begin(),lis.end(),x);if(itlis.end()){lis.push_back(x);}else{*itx;}}coutlis.size()endl;return0;}javaimportjava.io.*;importjava.util.*;publicclassMain{staticclassNode{longu;// T - Xlongv;// T XNode(longu,longv){this.uu;this.vv;}}publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));intNInteger.parseInt(br.readLine());Node[]anewNode[N];// Ti - Tj |Xi - Xj| Ti - Xi Tj - Xj and Ti Xi Tj Xjfor(inti0;iN;i){String[]partsbr.readLine().split( );longTLong.parseLong(parts[0]);longXLong.parseLong(parts[1]);a[i]newNode(T-X,TX);}Arrays.sort(a,(x,y)-{if(x.u!y.u){returnLong.compare(x.u,y.u);}returnLong.compare(y.v,x.v);});// 求v的严格递增子序列长度 lis[i]代表长度为i的可取最小值ArrayListLonglisnewArrayList();for(Nodep:a){longxp.v;intl0;intrlis.size();while(lr){intmid(lr)/2;if(lis.get(mid)x){rmid;}else{lmid1;}}if(llis.size()){lis.add(x);}else{lis.set(l,x);}}System.out.println(lis.size());}}pythonimportsysimportbisectclassNode:def__init__(self,u,v):self.uu# T - Xself.vv# T Xinputsys.stdin.readline Nint(input())a[]# Ti - Tj |Xi - Xj| Ti - Xi Tj - Xj and Ti Xi Tj Xjfor_inrange(N):T,Xmap(int,input().split())a.append(Node(T-X,TX))# u升序# u相同时v降序a.sort(keylambdap:(p.u,-p.v))# 求v的严格递增子序列长度 lis[i]代表长度为i的可取最小值lis[]forpina:xp.v# lower_boundidxbisect.bisect_left(lis,x)ifidxlen(lis):lis.append(x)else:lis[idx]xprint(len(lis))javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinput[];rl.on(line,line{input.push(line);});rl.on(close,(){letidx0;classNode{constructor(u,v){this.uu;// T - Xthis.vv;// T X}}constNNumber(input[idx]);leta[];// Ti - Tj |Xi - Xj| Ti - Xi Tj - Xj and Ti Xi Tj Xjfor(leti0;iN;i){let[T,X]input[idx].split( ).map(Number);a.push(newNode(T-X,TX));}a.sort((a,b){if(a.u!b.u){returna.u-b.u;}returnb.v-a.v;});// 求v的严格递增子序列长度 lis[i]代表长度为i的可取最小值letlis[];for(letpofa){letxp.v;// lower_boundletl0;letrlis.length;while(lr){letmid(lr)1;if(lis[mid]x){rmid;}else{lmid1;}}if(llis.length){lis.push(x);}else{lis[l]x;}}console.log(lis.length);});Gopackagemainimport(bufiofmtossort)typeNodestruct{uint64// T - Xvint64// T X}funcmain(){in:bufio.NewReader(os.Stdin)varNintfmt.Fscan(in,N)a:make([]Node,N)// Ti - Tj |Xi - Xj| Ti - Xi Tj - Xj and Ti Xi Tj Xjfori:0;iN;i{varT,Xint64fmt.Fscan(in,T,X)a[i]Node{u:T-X,v:TX,}}sort.Slice(a,func(i,jint)bool{ifa[i].u!a[j].u{returna[i].ua[j].u}returna[i].va[j].v})// 求v的严格递增子序列长度 lis[i]代表长度为i的可取最小值lis:make([]int64,0)for_,p:rangea{x:p.v// lower_boundl:0r:len(lis)forlr{mid:(lr)/2iflis[mid]x{rmid}else{lmid1}}ifllen(lis){lisappend(lis,x)}else{lis[l]x}}out:bufio.NewWriter(os.Stdout)deferout.Flush()fmt.Fprintln(out,len(lis))}
拼多多笔试真题-多多接金币(C++/Py/Java /Js/Go)
多多接金币拼多多技术岗 7月19号笔试 第三题题目内容多多在玩一个横版视角的接金币游戏控制的角色可以向左或者向右移动最大移动速度为111个单位距离/秒地图上总共会出现NNN枚金币第iii枚金币会在TiT_iTi秒时准确掉落在坐标XiX_iXi的位置如果没被接住就会瞬间消失。为了接住金币你必须在TiT_iTi秒时出现在XiX_iXi坐标。此外由于角色捡金币需要短暂的硬直时间如果你接住了金币AAA想要再去接金币BBB两次的时间间隔必须严格大于你在两地之间移动所需的时间即满足公式TB−TA∣XB−XA∣T_B - T_A |X_B - X_A|TB−TA∣XB−XA∣假设游戏开始前你可以在任意位置等待。请问你整场游戏最多能接住多少枚金币注意如果同一时刻坐标XXX有多枚金币同时掉落最多只可以接到一个。输入描述第一行包含一个整数N(1≤N≤105)N(1 \le N \le 10^5)N(1≤N≤105)表示金币的数量。接下来NNN行每行两个整数TiT_iTi和XiX_iXi1≤Ti≤1091 \le T_i \le 10^91≤Ti≤109−109≤Xi≤109-10^9 \le X_i \le 10^9−109≤Xi≤109分别表示金币出现时刻和坐标。输出描述输出一个整数表示你最多能收集到的金币数量。样例1输入5 1 2 5 5 2 3 7 4 6 8输出3说明最优接金币路径之一为提取【金币1】→【金币2】→【金币4】总共333枚。题解思路解题思路:逻辑分析 LIS算法题目限制两个金币先后获取的限制为TB−TA∣XB−XA∣T_B - T_A |X_B - X_A|TB−TA∣XB−XA∣,表达式展开为Ti - Xi Tj - XjTi Xi Tj Xj同时满足上述两个表达式即可进行拾取可以设置u Ti - Xiv Ti Xi现在要求最长二维链(A1,B1),(A2,B2),...,(Ak,Bk)需要同时满足A1A2…AkB1B2…Bk目前问题就转换为LIS问题处理逻辑为要实现求v的严格递增子序列长度需要按照u进行升序u相同情况按照v降序(避免u相同情况).然后使用二分求LIS进行求解即可。代码时间复杂度为O(nlogn)C#includebits/stdc.husingnamespacestd;usinglllonglong;structNode{ll u;// T - Xll v;// T X};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;cinN;vectorNodea(N);// Ti - Tj |Xi - Xj| Ti - Xi Tj - Xj and Ti Xi Tj Xjfor(inti0;iN;i){ll T,X;cinTX;a[i].uT-X;a[i].vTX;}sort(a.begin(),a.end(),[](constNodea,constNodeb){if(a.u!b.u){returna.ub.u;}returna.vb.v;});// 求v的严格递增子序列长度 lis[i]代表长度为i的可取最小值vectorlllis;for(autop:a){ll xp.v;autoitlower_bound(lis.begin(),lis.end(),x);if(itlis.end()){lis.push_back(x);}else{*itx;}}coutlis.size()endl;return0;}javaimportjava.io.*;importjava.util.*;publicclassMain{staticclassNode{longu;// T - Xlongv;// T XNode(longu,longv){this.uu;this.vv;}}publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));intNInteger.parseInt(br.readLine());Node[]anewNode[N];// Ti - Tj |Xi - Xj| Ti - Xi Tj - Xj and Ti Xi Tj Xjfor(inti0;iN;i){String[]partsbr.readLine().split( );longTLong.parseLong(parts[0]);longXLong.parseLong(parts[1]);a[i]newNode(T-X,TX);}Arrays.sort(a,(x,y)-{if(x.u!y.u){returnLong.compare(x.u,y.u);}returnLong.compare(y.v,x.v);});// 求v的严格递增子序列长度 lis[i]代表长度为i的可取最小值ArrayListLonglisnewArrayList();for(Nodep:a){longxp.v;intl0;intrlis.size();while(lr){intmid(lr)/2;if(lis.get(mid)x){rmid;}else{lmid1;}}if(llis.size()){lis.add(x);}else{lis.set(l,x);}}System.out.println(lis.size());}}pythonimportsysimportbisectclassNode:def__init__(self,u,v):self.uu# T - Xself.vv# T Xinputsys.stdin.readline Nint(input())a[]# Ti - Tj |Xi - Xj| Ti - Xi Tj - Xj and Ti Xi Tj Xjfor_inrange(N):T,Xmap(int,input().split())a.append(Node(T-X,TX))# u升序# u相同时v降序a.sort(keylambdap:(p.u,-p.v))# 求v的严格递增子序列长度 lis[i]代表长度为i的可取最小值lis[]forpina:xp.v# lower_boundidxbisect.bisect_left(lis,x)ifidxlen(lis):lis.append(x)else:lis[idx]xprint(len(lis))javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinput[];rl.on(line,line{input.push(line);});rl.on(close,(){letidx0;classNode{constructor(u,v){this.uu;// T - Xthis.vv;// T X}}constNNumber(input[idx]);leta[];// Ti - Tj |Xi - Xj| Ti - Xi Tj - Xj and Ti Xi Tj Xjfor(leti0;iN;i){let[T,X]input[idx].split( ).map(Number);a.push(newNode(T-X,TX));}a.sort((a,b){if(a.u!b.u){returna.u-b.u;}returnb.v-a.v;});// 求v的严格递增子序列长度 lis[i]代表长度为i的可取最小值letlis[];for(letpofa){letxp.v;// lower_boundletl0;letrlis.length;while(lr){letmid(lr)1;if(lis[mid]x){rmid;}else{lmid1;}}if(llis.length){lis.push(x);}else{lis[l]x;}}console.log(lis.length);});Gopackagemainimport(bufiofmtossort)typeNodestruct{uint64// T - Xvint64// T X}funcmain(){in:bufio.NewReader(os.Stdin)varNintfmt.Fscan(in,N)a:make([]Node,N)// Ti - Tj |Xi - Xj| Ti - Xi Tj - Xj and Ti Xi Tj Xjfori:0;iN;i{varT,Xint64fmt.Fscan(in,T,X)a[i]Node{u:T-X,v:TX,}}sort.Slice(a,func(i,jint)bool{ifa[i].u!a[j].u{returna[i].ua[j].u}returna[i].va[j].v})// 求v的严格递增子序列长度 lis[i]代表长度为i的可取最小值lis:make([]int64,0)for_,p:rangea{x:p.v// lower_boundl:0r:len(lis)forlr{mid:(lr)/2iflis[mid]x{rmid}else{lmid1}}ifllen(lis){lisappend(lis,x)}else{lis[l]x}}out:bufio.NewWriter(os.Stdout)deferout.Flush()fmt.Fprintln(out,len(lis))}
