腾讯2020秋招笔试真题

1、电话号码

【题目描述】企鹅王国是一个奇特的国家，他们的电话号码包含11位数字，并且第一个数字一定是8。比如88888888888就是企鹅王国的电话号码，但是13888888888和000就不是。
现在给出一个长度为n的字符串s，这个字符串只包含数字。
每一次操作，你可以从这个字符串中删除任意一个字符。

对于给定的字符串，需要你判断是否能通过0次或若干次操作，把这个字符串变成企鹅王国的电话号码。

输入描述

第一行一个整数t，表示测试用例的组数；
接下来2∗t行，每个测试用例包含2行；
第一行一个整数n，表示字符串的长度；
第二行一个字符串s。
输入满足1<=t<=100,1<=n<=100，每个字符串只包含数字。

输出描述

能则输出"YES"，否则输出"NO"。

示例1

输入

2
11
88888888888
3
000

输出

YES
NO

【解题思路】

按题意模拟实现即可。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        string s;
        cin >> s;
        if (s[0] == '8') {
            int sz = s.size();
            if (sz >= 11)
                puts("YES");
            else
                puts("NO");
        } else {
            int ma = -1;
            int sz = s.size();
            for (int i = 0; i < sz; i++) {
                if (s[i] == '8') {
                    ma = i;
                    break;
                }
            }
            if (ma == -1 || sz - ma < 11)
                puts("NO");
            else
                puts("YES");
        }
    }
    return 0;
}

2、两两配对

【题目描述】小Q有M(M为偶数)名员工, 第i名员工完成工作的时候有一个拖延时间值t_i。
现在小Q手里有M/2份工作需要完成, 每一份工作都需要安排两名员工参与, 对于第i份工作所需完成的时间为两名员工的拖延时间值总和。

现在M/2份工作同时开始进行,小Q希望所有工作结束的时间尽量早, 请你帮小Q设计一个优秀的员工分配方案,使得用尽量少的时间完成所有工作,并输出工作所需的最短时间。

输入描述

第一行为一个正整数n(1<=n<=10⁵)。
接下来有n行，每行两个正整数x和y，表示有x名员工的拖延时间值为y(1<=y<=10⁹)。保证所有x的总和等于M(2<=M<=10⁹), 保证M为偶数。

输出描述

输出工作所需的最短时间。

示例1

输入

3
1 8
2 5
1 2

输出

10

说明

拖延值为8的和拖延值为2的组队，两名拖延值为5的组队，所以完成工作的时间为10，这是时间最短的方案。

【解题思路】

贪心。最大的和最小的组合，次大的和次小的组合。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
struct node {
    int cnt, t;
} s[100001];
bool comp(node x, node y) { return x.t < y.t; }
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &s[i].cnt, &s[i].t);
    sort(s + 1, s + n + 1, comp);
    int minimum_t = 0;
    for (int left = 1, right = n; left <= right;) {
        int number = min(s[left].cnt, s[right].cnt);
        number /= (left == right) ? 2 : 1;
        minimum_t = max(minimum_t, s[left].t + s[right].t);
        s[left].cnt -= number;
        s[right].cnt -= number;
        left += (s[left].cnt == 0) ? 1 : 0;
        right += (s[right].cnt == 0) ? -1 : 0;
    }
    printf("%d", minimum_t);
}

3、分组

【题目描述】2020年一共有n名员工参加入职培训，第i名员工拥有一个战力值x[i]。
在入职培训中有一个小活动需要把所有员工分为A、B两组进行比拼对决。
为了让活动更有趣味性，小Q希望两组的人数尽量均分(即两组人数之差不超过1)，并且要让两组尽量势均力敌(A组的战力值之和与B组的战力值之和的差值尽量小)。
小Q把这个问题交给你了，希望你帮他完成这个分组问题。

输入描述

输入的第一行包含一个正整数T(1<=T<=10),表示测试用例数。
对于每一组测试用例，输入的一行包括一个正整数n(2<=n<=100),表示员工的数量。

接下来的一行,包含n个正整数x[i](1<=x[i]<=10⁵）

保证所有员工的战力值之和小于等于10⁵。

输出描述

输出两个整数, 从小到大依次输出两组的战力值之和。

示例1

输入

2
4
5 9 4 7
8
9 13 18 10 12 4 18 3

输出

12 13
43 44

【解题思路】

第i个人的权值记为a[i]，令