0922字节跳动笔试100+100+90+8

第一题，100%

先判断距离右边最近的厕所，然后从左往右遍历，比较距离左右厕所的最小值，输出。

#include<bits/stdc++.h>
#define INF 10000000
using namespace std;
typedef long long ll;
int main(){
    int n;
    string s;
    cin >> n >> s;
    vector<int> right(n, INF);
    int p = INF;
    for(int i = n - 1; i >= 0; i--){
        if(s[i] == 'O'){
            p = i;
        }
        right[i] = p - i;
    }
    p = -INF;
    for(int i = 0; i < n; i++){
        if(s[i] == 'O'){
            p = i;
        }
        cout << min(i - p, right[i]) << " ";
    }
    return 0;
}

第二题100%

优先队列，每次pop掉最大的，注意pop掉的后面要放回去，因为本身t可能很大。我这里直接把全部都放回去，发现也过了，挺暴力的。按道理还是应该比较处理下。

#include<bits/stdc++.h>
#define INF 10000000
using namespace std;
typedef long long ll;
int main(){
    int T, n, time, t;
    cin >> T;
    while(T--){
        cin >> n >> time;
        priority_queue<int> q;
        ll sum = 0;
        for(int i = 0; i < n; i++){
            cin >> t;
            vector<int> v;
            while(sum + t > time){ // 
                sum -= q.top();
                v.emplace_back(q.top());
                q.pop();
            }
            cout << i - q.size() << " "; // 输出结果
            v.emplace_back(t);
            for(auto t : v){ //全部放回去，挺暴力的
                q.push(t);
                sum += t;
            }
        }
        cout << endl;
    }
    return 0;
}

第三题90% 不知道哪里错了。

拓扑排序，每次找到入度为0的点，进行排序。

坑：

1，输入的问题，有点坑.

2，输出问题，最后不能有空格

3，这道题直接输出-1得50%。

4，最大的坑，没告诉数据范围，差点想用map了，想了下数据应该不太强，就没用，数组开大。

5，用set来找入度为0的点，这样找到就是最小的点。找到就break,，然后删除他。

#include<bits/stdc++.h>
#define INF 10000000
using namespace std;
typedef long long ll;
const int N = 1000000;
int main(){
    string s;
    int t, tmp;
    vector<vector<int>> v(N);
    vector<int> indegree(N, 0);
    set<int> si;
    while(getline(cin, s)){
        istringstream ss(s);
        ss >> tmp;
        si.insert(tmp);
        while(ss >> t){
            v[t].push_back(tmp);// t - > tmp
            indegree[tmp]++;
            si.insert(t);
        }
    }
    int size = (int)si.size();
    
    queue<int> q;
    for(auto a : si){
        if(indegree[a] == 0){
            q.push(a);
            si.erase(a);
            break;
        }
    }
    vector<int> re;
    while(!q.empty()){
        int f = q.front(); q.pop();
        re.emplace_back(f);
        for(auto a : v[f]){
            indegree[a]--;
        }
        for(auto a : si){
            if(indegree[a] == 0){
                q.push(a);
                si.erase(a);
                break;
            }
        }
    }
    if(re.size() == size){
        cout << re[0];
        for(int i = 1; i < size; i++) cout  << " " << re[i];
        cout<<endl;
    }else{
        cout<<-1<<endl;
    }
    return 0;
}

第四题，8%

思路：无

不会，应该是dp? 随便写了点，输出max(a,b)，过了8%，就不贴代码了，太菜了哎。

#笔试题目##字节跳动#