网易2020秋招笔试真题

1、最小数位和

【题目描述】定义S(n)，表示n在十进制下的各位数字和。

现在给定一个x,请你求出最小正整数n，满足x≤S(n).

输入描述

第一行数据组数T，对于每组数据，一行一个数字x。

1≤x≤10⁵,1≤T≤10

输出描述

对于每组数据，一行一个整数表示最小的n。

示例1

输入

2
7
9 

输出

7
9

示例2

输入

2 
13
18

输出

49  
99

【解题思路】

构造题。10进制最大数是9，所以求9的除数就有几个9，余数就是最大位的数。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
int t;
void solve() {
    int x;
    scanf("%d", &x);
    if (x % 9)
        printf("%d", x % 9);
    x -= x % 9;
    for (int i = 1; i <= x / 9; i++)
        printf("9");
    printf("\n");
}
int main() {
    scanf("%d", &t);
    while (t--)
        solve();
    return 0;
}

2、吃葡萄

【题目描述】有三种葡萄，每种分别有a,b,c颗。有三个人，第一个人只吃第1,2种葡萄，第二个人只吃第2,3种葡萄，第三个人只吃第1,3种葡萄。
适当安排三个人使得吃完所有的葡萄,并且且三个人中吃的最多的那个人吃得尽量少。

输入描述

第一行数字T，表示数据组数。

接下来T行，每行三个数a,b,c

1≤a,b,c≤10¹⁸,1≤T≤10

输出描述

对于每组数据，输出一行一个数字表示三个人中吃的最多的那个人吃的数量。

示例1

输入

2
1 2 3
1 2 6

输出

2
3

示例2

输入

1
12 13 11

输出

12

【解题思路】

可以看成是三个人分别站在三角形的顶点（假定可以形成三角形）。设三角形两个短边是a,b，长边是c。则，若两短边之和大于等于长边的一半，可实现总数平分；反之，则结果为长边的一半。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll up(ll a, ll b) {
    if (a % b)
        return a / b + 1;
    return a / b;
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        ll a, b, c;
        cin >> a >> b >> c;
        ll mx = max(max(a, b), c);
        ll ans = max(up(mx, 2), up(a + b + c, 3));
        cout << ans << endl;
    }
    return 0;
}

3、圆环切割

【题目描述】小易有n个数字排成一个环，你能否将它们分成连续的两个部分(即在环上必须连续)，使得两部分的和相等？

输入描述

第一行数据组数T，对于每组数据
第一行数字n，表示数字个数

接下来一行n个数，按顺序给出环上的数字。

2≤n≤100000,1≤A_i≤109

输出描述

对于每组数据，一行输出YES/NO

示例1

输入

1 
6
1 2 3 4 5 6

输出

NO

示例2

输入

1
4
4 4 5 3

输出

YES

【解题思路】

维护出前缀和数组，然后通过set容器做一个hash查找看是否能完成切割。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
int n;
#define ll long long
ll sum[100005];
set<ll> st;
void solve() {
    scanf("%d", &n);
    memset(sum, 0, sizeof(sum));
    st.clear();
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        sum[i] = sum[i - 1] + x;
    }
    if (sum[n] & 1) {
        puts("NO");
        return;
    }
    for (in