来来来 链家笔试交流

你这的第二题。。。。还需要用算法？？直接STL的set集合输出不就完了。、、三个题目***了。。。没有一丁点含金量、、、

package com.zhenti.lianjia; import java.util.Arrays; import java.util.Scanner; public class t2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] aSum = new int[n]; for (int i = 0; i < n; i++) { int tmp = sc.nextInt(); aSum[i] = i > 0 ? aSum[i - 1] + tmp : tmp; } int qn = sc.nextInt(); for (int i = 0; i < qn; i++) { int i1 = Arrays.binarySearch(aSum, sc.nextInt()); if (i1 < 0) System.out.println(-i1); else System.out.println(i1 + 1); } } } //5//2 7 3 4 9//3//1 25 11

你的第三题是我的第一题，第二题是我的第三题

对对对，他需要找会多线程的人优化他的系统(😂😂😂)

// 思路： 排序 + hash #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <vector> #include <string> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_set> #include <unordered_map> #include <algorithm> using namespace std; const int maxn = 100000 + 5; long long arr[maxn]; long long brr[maxn]; long long crr[maxn]; int main() { int n; cin >> n; arr[0] = 0; for(int i = 1; i <= n; i++) cin >> arr[i]; for(int i = 2; i <= n; i++) arr[i] = arr[i] + arr[i-1]; int m; cin >> m; for(int i = 1; i <= m; i++) { cin >> brr[i]; crr[i] = brr[i]; } unordered_map<long long, long long> mm; sort(crr+1, crr+m+1); int pos = 1; int i = 1; while(i <= n) { if(pos > m) break; while(arr[i] < crr[pos]) i++; mm[crr[pos]] = i; pos++; } for(int i = 1; i <= m; i++) cout << mm[brr[i]] << endl; return 0; } // 剩八分钟时写好的， 没敢提交，不知能不能100%。（谁知道这种OJ需要排队到什么时候， 谁知道最后卷子交不上咋整？）， 没想到最后延时了， 哭瞎在风中~~~~

第一题我记得是100%。思路是预读入所有查询，然后由小到大排序。再从小到大遍历一遍所有区间，边遍历边从排好序的查询中不断拿出这区间的查询。 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; for (int i = 0; i < n; ++i) { a[i] = sc.nextInt(); } int apl[] = new int[n]; apl[0] = a[0]; for (int i = 1; i < n; ++i) { apl[i] = apl[i - 1] + a[i]; } int m = sc.nextInt(); Node nodes[] = new Node[m]; for (int i = 0; i < m; ++i) { int c = sc.nextInt(); nodes[i] = new Node(c, i); } Arrays.sort(nodes, new Node(0, 0)); int cur = 0; for (int i = 0; i < n; ++i) { int left = i == 0 ? 1 : apl[i - 1] + 1; int right = apl[i]; while (nodes[cur].value <= right && nodes[cur].value >= left) { nodes[cur].ord = i + 1; nodes[cur].value = nodes[cur].index; if (++cur == m) break; } if (cur == m) break; } Arrays.sort(nodes, new Node(0, 0)); for (int i = 0; i < m; ++i) System.out.println(nodes[i].ord); } } class Node implements Comparator<Node> { int value; int index; int ord; public Node(int a, int b) { value = a; index = b; } public int compare(Node o1, Node o2) { return o1.value - o2.value; } }

把第一题发来看看

去重和排序  set最6

第一题，应评论区要求，贴一下；特别是那个多线程的，现在这方面水平不高，求喷求指正 //普通版（大量查询会超时，过了82%） #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin>>n; vector<int> everysum(n,0); for(int i=0;i<n;++i){ cin>>everysum[i]; } for(int i=1;i<n;++i){ everysum[i]+=everysum[i-1]; } int Q; cin>>Q; vector<int> Query(Q); for(int i=0;i<Q;++i){ cin>>Query[i]; } for(int i=0;i<Q;++i){ int result; vector<int>::iterator it; it=lower_bound(everysum.begin(),everysum.end(),Query[i]); if(it==everysum.end()) result=n; else result=(int)(it-everysum.begin()+1); cout<<result<<endl; } return 0; } //多线程版（可能有错，以前没怎么写过，这个还没测试，欢迎指正） #include <iostream> #include <vector> #include <algorithm> #include <thread> using namespace std; void thread_task(vector<int>& everysum,vector<int>& Query,vector<int>& group,int start,int end,int n){ for(int i=start;i<end;++start){ vector<int>::iterator it; it=lower_bound(everysum.begin(),everysum.end(),Query[start]); if(it==everysum.end()) group[start]=n; else group[start]=(int)(it-everysum.begin()+1); } } int main() { int n; cin>>n; vector<int> everysum(n); cin>>everysum[0]; for(int i=1;i<n;++i){ int tmp; cin>>tmp; everysum[i]=everysum[i-1]+tmp; } int Q; cin>>Q; vector<int> Query(Q); for(int i=0;i<Q;++i){ cin>>Query[i]; } if(Q>1000){//大于1000就开多线程 vector<int> group(Q); int numOfThread=Q/1000; for(int i=0;i<numOfThread;++i){ int start=i*1000; int end=start+1000; thread t(thread_task(everysum,Query,group,start,end,n)); t.join(); } thread t(thread_task(everysum,Query,group,numOfThread*1000+1,Q,n)); t.join(); for(int val:group){ cout<<val<<endl; } } else{//小于1000就没必要开线程了 for(int i=0;i<Q;++i){ int result; vector<int>::iterator it; it=lower_bound(everysum.begin(),everysum.end(),Query[i]); if(it==everysum.end()) result=n; else result=(int)(it-everysum.begin()+1); cout<<result<<endl; } } return 0; }

我用sort一直不让我用啊

搞得我自己写了个快排。。。

我一脸懵逼，直到最后都没有提交上去

其实原先就觉得用sort,qsort也太猥琐了，没想到前面还有直接用set的。还有拿到摘苹果也太逗比了吧，我都不敢信。链家这个编程题666

第一题，开个大数组，输入时顺便记录下每个数字的分组，查询时直接输出按照下标索引得到的分组编号，提交是AC的。

//室友报的，只能自己在IDE上尝试，也不知道方法可不可以，发出来求各位大神指教一下 每次将待查询的数（query）与之前每组的个数（group）做比较，若比个数大，则减去group数组的值，直到小于group的值，则落在那俩个数的区间，即得到组号。 思路比较乱，代码略渣，见谅。 using namespace std; int main(){ int n; cin>>n; int group[n]; for(int i = 0;i<n;i++){ cin>>group[i]; } int q; cin>>q; int query[q]; for(int i = 0;i<q;i++){ cin>>query[i]; } int result[q]; for(int i = 0;i<q;i++){ int j = 0; while(query[i]>group[j]){ query[i] -= group[j]; j++; } result[i] = j+1; } for(int i = 0;i<q;i++) if(i<q-1) cout<<result[i]<<' '; else cout<<result[i]; return 0; }

第一题，我现在的想法是，定义一个结构体，结构体有两个值，一个放编号，另一个放序号，然后将所有的分组数读入到结构体中，最后用二分法查询各个值，并将序号输出，不知道这个思路能不能AC，当时也是过了82