头条笔试总结

总得来说还行吧，运气比较好，就是时间太少了，多10min不知道能AK不

由于没有存代码！所以就不贴代码了，只有第四题存有代码，但是没AC...，比赛结束后才调试好的

第一题：给n个数，求差值为k的数字对去重后的个数

　　　　很简单的题，看一眼就会，sort+hash_map瞎搞就行了，注意这里卡常....，笔试时用快读+unordered_set还是只过90%，最后i++改成++i才通过的( ps:以后再也不写i++了

第二题：题目有点忘了，随便打个表就过了

第三题：给一个表达式，只有6，*，+，- 四种字符，要求用题目给的表打印结果。如下

　　　　很简单，两个栈一个存数字一个存符号，循环两次，第一次计算*号，第二次计算+-，最后对结果输出就好了，注意0即可

第四题：有两个集合A,B，这里假设集合A的平均值大于集合B，那么每次可以从集合A取一个值放入集合B，使得两个集合的平均值变大（注意：如果集合B中存在集合A要放入的数，则集合B的平均值不变，即集合求平均值的时候，重复的数不统计在内

　　　　（我觉得一直二分就行了！附上SB代码，不知道能AC不

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <map>
 5 using namespace std;
 6 typedef long long ll;
 7 const int SIZE = 1e5+7;
 8 int a[SIZE],b[SIZE],c[SIZE];
 9 map < int,int > mp;
10 
11 int binsearch(int l,int r,int v){
12     if(l > r){
13         if(c[r] > v) return r;
14         return l;
15     }
16     int mid = (l+r)/2;
17     if(c[mid] <= v) return binsearch(mid+1,r,v);
18     else return binsearch(l,mid-1,v);
19 }
20 
21 int main(){
22     int n,m;
23     scanf("%d%d",&n,&m);
24     ll av1 = 0;
25     ll av2 = 0;
26     for(int i=0;i<n;++i){
27         scanf("%d",&a[i]);
28         av1 += a[i];
29     }
30     for(int i=0;i<m;++i){
31         scanf("%d",&b[i]);
32         av2 += b[i];
33     }
34     sort(a,a+n);
35     sort(b,b+m);
36 
37     int len,avg,flag;
38     if(av1/n > av2/m){
39         flag = av1 / n;
40         avg = av2 / m;
41         len = n;
42         for(int i=0;i<n;++i){
43             c[i] = a[i];
44             mp[c[i]] ++;
45         }
46     }
47     else{
48         flag = av2 / m;
49         avg = av1 / n;
50         len = m;
51         for(int i=0;i<m;++i){
52             c[i] = b[i];
53             mp[c[i]] ++;
54         }
55     }
56 
57     int ans = 0;
58     while(1){
59         int id = binsearch(0,len,avg);
60         if(c[id] >= flag) break;
61         if(mp[c[id]] > 1){
62             avg = c[id];
63             continue;
64         }
65         ++ ans;
66         if(av1/n > av2/m){
67             av2 += c[id];
68             av1 -= c[id];
69             for(int i=id;i<n;++i)
70                 c[i] = c[i+1];
71             m ++;
72             n --;
73             len = n;
74             avg = av2 / m;
75             flag = av1 / n;
76             if(av1 % n) flag ++;
77         }
78         else{
79             av1 += c[id];
80             av2 -= c[id];
81             for(int i=id;i<m;++i)
82                 c[i] = c[i+1];
83             m --;
84             n ++;
85             len = m;
86             avg = av1 / n;
87             flag = av2 / m ;
88             if(av2 % m) flag ++;
89         }
90     }
91     printf("%d
",ans);
92     return 0;
93 }
94 /* 3 5
95  1 2  5
96 2 3 4 5 6
97 2*/

第五题：给n个跳板，可以跳k次，每次能跳到距离当前位置h以内的跳板，如果跳到一个跳板，则能跳跃的高度是，本身位置到跳板位置的两倍。如现在在位置1，跳板高度为3，那么能通过使用这个跳板跳跃到高度为5的位置

　　　　无脑bfs即可，但我感觉数据很水，我不确定我的代码是否能AC的时候AC了