百度2020秋招笔试真题

1、度度熊的工作

【题目描述】老板给度度熊分配了n个工作，第i个工作需要耗费a_i单位时间，每个工作必须老板给定的限制时间b_i前完成。
度度熊从0时刻开始工作，在同一时间度度熊手上只能做一件工作，度度熊想知道他是否能把所有工作都完成呢？

输入描述

第一行一个数T表示数据组数。 (1≤T≤10)
每组数据第一行一个数n。 (1≤n≤2×105)
接下来n行每行两个数表示a_i，b_i。 (1≤a_i,b_i≤109)

输出描述

每组数据输出一行，如果度度熊能完成他的工作输出"Yes"不然输出“No”。

示例1

输入

输出

Yes

说明

从前往后依次做每个工作即可完成。

【解题思路】

用堆贪心实现。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
 
const int Maxn = 2e5;
int N;
struct Node {
    int t1, t2;
    bool operator<(const Node &rhs) const { return t2 < rhs.t2; }
} A[2 * Maxn + 5];
priority_queue<int> q;
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        for (int i = 1; i <= N; i++)
            scanf("%d %d", &A[i].t1, &A[i].t2);
        sort(A + 1, A + N + 1);
        int t = 0, tot = 0;
        if (!q.empty())
            q.pop();
        for (int i = 1; i <= N; i++) {
            if (t + A[i].t1 <= A[i].t2) {
                tot++;
                t += A[i].t1;
                q.push(A[i].t1);
            } else {
                if (q.empty())
                    continue;
                int maxx = q.top();
                if (A[i].t1 < maxx) {
                    q.pop();
                    q.push(A[i].t1);
                    t = t - maxx + A[i].t1;
                }
            }
        }
        if (tot == N)
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

2、小度部队

【题目描述】小度的特种部队一共有n名士兵, 一天小度派所有士兵去探索野区。士兵们出发时沿着一条道路行进, 直到遇到三岔路口。
小度在出发前就给部队部署了部队划分规则:当遇到三岔路口的时候, 部队若可以分为两个部分，并且两个部分的人数差恰好为k,那么就完成部队划分,划分的两个部分分别沿着两条路行进下去，否则该部队的所有士兵就在此位置停下扎营。
野区内有不计其数的三岔路口, 所以整个部队的每一个部分最终都会停下扎营，小度想知道最终扎营的总数为多少？

输入描述

包括两个整数n,k(1<=n<=10^9, 1<= k<=1000), 即部队中士兵的总人数和划分部队的参数。

输出描述

一个整数，表示最终答案。

示例1

输入

10 2

输出

说明

10
/ \
6 4
/\ /\
4 2 3 1
/\
3 1
最终叶子节点个数即答案:5

【解题思路】

递归搜索所有情况即可。

【参考代码】

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
ll k, n;
ll dfs(int v) {
    if (v <= k)
        return 1;
    if ((v - k) % 2 == 0)
        return (dfs((v - k) / 2) + dfs((v + k) / 2));
    else
        return 1;
}
int main() {
    scanf("%lld%lld", &n, &k);
    printf("%lld", dfs(n));
    return 0;
}