• 20240117更新
  2024年秋招笔试题目，没想到时隔几个月字节跳动游戏业务就要寄了，本文仅供参考，请大佬多多指教

Q1字符串处理

Q2 杯子问题

桌子上有410^9+1个饮料杯，这些饮料杯的编号依次为-210^9~2*10^9，有的盛有饮料，有的是空杯子。现在，牛牛想将一些饮料杯中的饮料倒入某些空杯中，以此来重新排列这些饮料的放置次序。牛牛想让这些饮料最终都盛放在 n 个不同的饮料杯中，并且这 n 个饮料杯编号依次相邻。对于每一次转移，牛牛只能将任何一个饮料杯中的饮料倒入任何一个空的饮料杯中。
求最少的转移次数？
输入描述
第一行输入盛有饮料的杯子数量N，随后N行，输入N个盛有饮料杯子的编号ai，保证没有两个ai是相同的
输出描述
输出饮料的最少的转移次数使得盛有饮料的杯子按照顺序排列

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    long long n;
    int num;
    cin >> n;
    vector<int> cups(n);
    for (int i = 0; i < n; i++) {
        cin >> num;
        cups[num]=1;
    }
    int left = 0, right = n - 1;
    int ans = 0;
    while (left <= right) {
        if (cups[left] > 0 && cups[right] < 0) {
            int min_val = min(abs(cups[left]), abs(cups[right]));
            cups[left] -= min_val;
            cups[right] += min_val;
            ans += min_val;
        }
        if (cups[left] <= 0) left++;
        if (cups[right] >= 0) right--;
    }
    cout << ans << endl;
    return 0;
}

一遍未果，发现理解有误，再拿贪心写一遍

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> cups(n);
    for (int i = 0; i < n; i++) {
        cin >> cups[i];
    }
    sort(cups.begin(), cups.end()); // 将饮料杯按编号从小到大排序
    int cur = cups[0]; // 当前已盛放饮料的杯子编号
    int moves = 0; // 转移次数
    for (int i = 1; i < n; i++) {
        if (cups[i] != cur + 1) { // 如果当前杯子编号不是上一个杯子编号加1，则需要转移饮料
            moves++;
        } else {
            cur++; // 否则当前杯子已经盛有饮料，更新当前已盛放饮料的杯子编号为当前杯子编号
        }
    }
    cout << moves << endl;
    return 0;
}

还是未果lol

Q3食堂打饭

由于某种众所周知的原因，食堂只开放了一个打饭窗口，已知一共会有 n 位学生陆陆续续进到食堂。
牛牛知道这 n 位学生的相关信息，首先将这 n 位学生编号为1,2,..., n .
每位学生的信息格式如下：
l ：到达食堂的时间。
s ：强壮程度。
a ：打饭耗时。
b ：用餐耗时。
r ( r > l )：开班会的时间。
学生按照到达食堂的时间进行排队，依次排到打饭窗口队伍的队尾，如果相同时间到达，则强壮程度值更高的排在前面，如果也同样强壮，则编号小排在前面。
当轮到某位学生打饭时，会耗费 a 个单位时间，之后立即轮到排在这位学生后面的学生打饭；
打完饭之后会耗费 b 个单位时间用餐。
当且仅当用完餐时，尚未开始班会，才有可能赶上，即：如果从 t 时刻开始打饭，那么，当且仅当 t + a + b < r 时，才有可能赶上班会，否则，他／她将选择不吃这顿饭，直接去班会地点。
一旦某位学生发现自己按照现有排队情况无法赶上班会，则他／她会直接走出队列，前往班会地点，即使已经轮到他／她打饭，他／她也会直接离开，不会产生任何其它时间消耗。
假设每一位学生都足够聪明，请你判断每位学生是否能够用餐。
本题为多组测试数据，第一行输入一个正整数 T (1≤ T ≤1000)，代表测试数据的组
数。
对于每组测试数据，第一行输入一个正整数
n (1≤ n ≤10°)，代表到食堂就餐的学生
数量。
接下去 n 行，第 i +1行输入五个正整数 l , s , a , b , r (1≤l, s , a , b ≤10^4;1≤ r ≤10^9;l< r )，表示编号为i的这位学生的相关信息，具体含义如题所述。
题目保证，所有测试数据的 n 之和不会超过10^5
输出描述
对于每组测试数据，一行输出一个长度为 n 的01串，其中，第i个字符为1，则说明编号为i的这位学生能够顺利用餐；否则，说明这位学生来不及用餐。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100005;

struct Student {
    int id; // 学生编号
    int l, s, a, b, r; // 到达时间、强壮程度、打饭时间、用餐时间、开班会时间
    int leave_time; // 离开食堂的时间
    bool able_to_eat; // 是否能够用餐

    bool operator<(const Student& other) const { // 排序规则
        if (l != other.l) return l < other.l;
        if (s != other.s) return s > other.s;
        return id < other.id;
    }
} students[MAXN];

int t, n;

inline int read() { // 快读
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

inline void write(int x) { // 快输
    if (x < 0) putchar('-'), x = -x;
    if (x >= 10) write(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    t = read();
    while (t--) {
        n = read();
        for (int i = 1; i <= n; i++) {
            students[i].id = i;
            students[i].l = read();
            students[i].s = read();
            students[i].a = read();
            students[i].b = read();
            students[i].r = read();
            students[i].leave_time = students[i].l + students[i].a + students[i].b; // 初始化离开时间
            students[i].able_to_eat = false; // 初始化为不能用餐
        }
        sort(students + 1, students + 1 + n);

        int cur_time = students[1].l; // 当前时间初始化为第一个学生到达的时间
        int q_head = 1, q_tail = 0; // 使用自己实现的队列，头指针和尾指针分别初始化为 1 和 0
        while (q_head <= n) {
        	cout<<"cur time:"<<cur_time<<" a:"<<students[q_head].a<<" b:"<<students[q_head].b<<endl;
            if (cur_time + students[q_head].a + students[q_head].b < students[q_head].r) { // 如果当前学生能够赶上班会
                cur_time += students[q_head].a; // 更新当前时间
                students[q_head].able_to_eat = true; // 标记为能够用餐
//                cout<<q_head<<" is true"<<endl;
                q_head++; // 处理下一个学生
                continue;
            }
//            cout<<"q_head:"<<q_head<<"tail:"<<q_tail<<endl;
            while (q_tail < n && cur_time >= students[q_tail + 1].leave_time) q_tail++; // 删除已经不能用餐的学生
            if (q_head <= q_tail) { // 队列非空
//            cout<<1<<" "<<cur_time<<endl;
                cur_time = max(students[q_tail + 1].l, cur_time); // 更新当前时间为队列中下一个学生到达的时间
                q_tail++; // 处理队首学生
            } else { // 队列
//			cout<<2<<" q_head:"<<q_head<<endl;
                cur_time = max(students[q_head].l,cur_time); // 更新当前时间为队首学生到达的时间
            }
            q_head++;
        }

        for (int i = 1; i <= n; i++) {
        	for(int j=1;j<=n;j++)
        	{
        		if(students[j].id==i){
            		write(students[j].able_to_eat); // 输出能否用餐的结果
            		continue;
            	}
        	}
        }
        puts(""); // 换行
    }

    return 0;
}

Q4方格问题

由 N 个1x1单元格组成的1 x N 的条形格，请你找到最大的 K ，使他满足将条形格分为一个1 x K 的区域，两个1x K -1的区域，三个1x K -2的区域．...... K 个1 x 1的区域。需要注意的是，这些区域不可接触。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int k = 1; // 初始化为1
    while (k * (k + 3) / 2 <= n) { // 计算条件，每次加1测试
        ++k;
    }

    cout << k - 1 << endl; // 输出结果

    return 0;
}

#include <iostream>
using namespace std;

bool check(int n, int k) {
    int i = 1, sum = 0;
    while (n > 0) {
        if (n <= k) return true; // 当前区域长度不超过k，可以分为一个区域
        sum += k + i;           // 累加当前区域的单元格数量
        n -= k + i;             // 计算下一个区域的起始位置
        i++;                    // 下一个区域比当前区域短1个单位长度
    }
    return false;
}

int main() {
    int n;
    cin >> n;

    int ans = 0;
    for (int k = 1; k <= n; k++) {
        if (check(n, k)) ans = k;
        else break;
    }
    cout << ans << endl;
    return 0;
}