字节跳动第六场笔试-2021春招研发岗

谁借莪１个温暖的怀抱￠ 2023-01-16 11:20 147阅读 0赞

# 1.小松鼠过冬 #

### 题意 ###

地上有n个洞穴，每个洞穴内有 a\[i\] 个松子，松鼠可以从任一洞穴中取若干个松子，向相邻洞穴搬运，使得每个洞穴中的松子数都相等（题目保证松子是平分的），问松子最少被移动的次数。例如，有4个洞穴的松子数为【9，9，15，7】，则最少移动次数为3。  
第一次，松鼠从第3个洞穴中拿3个松子移动到第4个洞穴；  
第二次，松鼠从第3个洞穴中拿2个松子移动到第2个洞穴；  
第三次，松鼠从第2个洞穴中拿1个松子移动到第1个洞穴；

### 样例输入 ###

4  
9 9 15 7

### 样例输出 ###

### 思路 ###

当时做的时候把它想复杂了，考试结束之后看大佬的思路是这样的，先计算松子的平均数，然后从头开始遍历数组，如果当前洞口的松子数不等于目标松子数，就cnt++，并且把当前松子和目标松子的差值转移到下一个洞，遍历到最后一个洞穴即可。

### 代码 ###

#include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<string>
    #include<algorithm>
    #include<queue>
    #include<math.h>
    #include<set>
    #include<time.h>
    #pragma GCC optimize(2)
    using namespace std;
    #define INF 1e9
    typedef long long ll;
    typedef unsigned long long ull;
    
    int main()
    {
        
        int n,a[1005];
        cin >> n;
        int sum = 0;
        for(int i = 0; i < n; i++) {
        
            cin >> a[i];
            sum += a[i];
        }
        int ave = sum / n;
        int cunt = 0;
        for(int i = 0; i < n-1; i++){
        
            int temp = a[i]-ave;
            a[i+1] += temp;
            cout << a[i+1] << endl;
            if(temp != 0){
        
                cunt++;
            }
        }
        cout << cunt << endl;
    }

# 2.配置文件 #

### 题意 ###

![配置文件][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy_size_16_color_FFFFFF_t_70]  
文件x以及继承自该文件的配置文件不再依赖根配置文件；输出每次修改后依赖根配置文件的文件数。

### 样例输入 ###

7  
0 1 1 3 3 2  
6  
3  
4  
5  
2  
1  
3

### 样例输出 ###

4  
4  
4  
2  
1  
1

### 思路 ###

我使用的是并查集，但复杂度较高，通过率是42%，网上说使用dfs+HashSet可以ac，我的是每次将要修改的文件的祖父节点置为-1，然后判断每个文件的祖父节点是不是0，如果是0，则代表依赖根配置文件；否则不依赖。

### 代码 ###

#include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<string>
    #include<algorithm>
    #include<queue>
    #include<math.h>
    #include<set>
    #include<time.h>
    #pragma GCC optimize(2)
    using namespace std;
    #define INF 1e9
    typedef long long ll;
    typedef unsigned long long ull;
    
    int f[1005];
    
    int findFather(int x){
        
        if(x == 0 || x == -1) return x;
        else return findFather(f[x]);
    }
    
    int Cunt(int n){
        
        int cunt = 1;
        for(int i = 1; i < n; i++){
        
            if(findFather(i) == 0) cunt++;
        }
        return cunt;
    }
    
    int main()
    {
        
        int n;
        cin >> n;
        f[0] = 0;
        for(int i = 1; i < n; i++) cin >> f[i];
        int q,x;
        cin >> q;
        while(q--){
        
            cin >> x;
            f[x] = -1;
            cout << Cunt(n) << endl;
        }
    }

# 3.排需求（请喝奶茶） #

### 题意 ###

小明要完成m个需求，每个需求需要处理 x 天 ，每个需求每处理1天就需要请相应的业务员喝 n 杯奶茶，小明每天只能处理1个需求，输入 t 组样例，每组样例包括天数和奶茶数，输出每组样例中处理需求的顺序，使得请喝的奶茶最少。

### 样例输入 ###

4  
4  
3 4  
1 100  
2 2  
5 5  
3  
1 1  
2 2  
3 3  
5  
3 2  
3 5  
365 999  
2 3  
1 1  
3  
123 123  
3 3  
5 5

### 样例输出 ###

2 1 3 4  
1 2 3  
3 2 4 5 1  
1 2 3

### 思路 ###

这题我当时在写时，算了很久只发现了如果所有的需求中天数和奶茶数相同时，顺序就是按原始序号顺序（1，2，3…）即可，但始终不知道其他的怎么解决，考试结束看到网上说用奶茶数 ÷ 天数，按从高到低排序即可，若值相同则按序号排序，就是最终处理需求的顺序（至于为啥是按奶茶数 ÷ 天数排序，我感觉是因为奶茶数 ÷ 天数指的是平均每天要请的奶茶数，然后平均每天要请的奶茶数越高的需求优先级越高，应该越先处理）。

### 代码 ###

#include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<string>
    #include<algorithm>
    #include<queue>
    #include<math.h>
    #include<set>
    #include<time.h>
    #pragma GCC optimize(2)
    using namespace std;
    #define INF 1e9
    typedef long long ll;
    typedef unsigned long long ull;
    
    struct milk
    {
        
        double x;
        int index;
    }s[1005];
    
    int cmp(milk s1,milk s2){
        
        if(s1.x == s2.x) return s1.index < s2.index;
        else return s1.x > s2.x;
    }
    
    int main()
    {
        
        int t,n;
        double a,b;
        cin >> t;
        while(t--){
        
            cin >> n;
            for(int i = 0; i < n; i++){
        
                cin >> a >> b;
                s[i].x = b/a;
                s[i].index = i+1;
            }
            sort(s,s+n,cmp);
            for(int i = 0; i < n-1; i++)
                cout << s[i].index << " ";
            cout << s[n-1].index << endl;
        }
    }

# 4.最美序列 #

### 题意 ###

一个长度为n的数组，a1，a2，a3，…`在这里插入代码片`…，an，从中找出一个子序列A（顺序与原序列保持一致，但不用连续），A\[i\] = A\[i-1\] \* A\[i-2\] mod 2021，找出数组中最长的这样子序列，输出A的所有情况数以及元素个数，n不超过100.

### 思路 ###

输入输出比较长，我也没记，网上说这道题使用的dp。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy_size_16_color_FFFFFF_t_70]: /images/20221022/748a3b3b94224df7857b62ccc286db08.png