【2021】贝壳找房春招C++工程师笔试卷2

• 完美序列
• 商场收益统计
• 大橘为重
• 叠大饼

输入例子1:

7 8
9 9 6 0 6 6 9

输出例子1:

3

例子说明1:
满足要求的是 [9,9,6]
输入例子2:

5 8
9 9 6 0 9

输出例子2:

5

例子说明2:
满足要求的是 [9 9 6 0 9]

思路：
前缀和，sum1分别为大于k的前缀和数组，sum2为小于k的前缀和数组，维护好前缀和数组之后暴力查找最大的序列长度即可。

#include
using namespace std;
const int maxn = 1e4+5;
int sum1[maxn] = {0}, sum2[maxn] = {0};
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    int a[n+1];
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if(a[i] > k) sum1[i]++;
        else sum2[i]++;
    }
    for(int i = 1; i <= n; i++) {
        sum1[i] += sum1[i-1];
        sum2[i] += sum2[i-1];
    }
    //for(int i = 0; i <= n; i++) cout << sum1[i] << " " << sum2[i] << endl;
    int ans = 0;
    for(int i = n; i >= 1; i--) {
        for(int j = 1; j < i; j++) {
            if(sum1[i] - sum1[j-1] > sum2[i] - sum2[j-1]) {
                ans = max(i - j + 1, ans);
            }
        }
    }
    printf("%d", ans);
    return 0;
}

输入例子1:

3 2
apple 1 10
pear 1 6
bike 100 1
apple 10
bike 1

输出例子1:

110

输入例子2:

3 2
apple 1 10
pear 1 6
bike 100 1
apple 10
bike 2

输出例子2:

-2

#include
using namespace std;
const int maxn = 1e5+10;
struct goods
{
    string name;
    int w;
    int c;
}a[maxn];
int n, m;
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        cin >> a[i].name;
        scanf("%d%d", &a[i].w, &a[i].c);
    }
    int ans = 0;
    bool flag = true;
    for(int i = 1; i <= m; i++) {
        string good;
        cin >> good;
        int x;
        scanf("%d", &x);
        for(int j = 1; j <= n; j++) {
            if(a[j].name == good) {
                if(x <= a[j].c) {
                    ans += x * a[j].w;
                    a[j].c -= x; 
                } else {
                    ans = -i;
                    flag = false;
                    break;
                }
            }
        }
        if(!flag) break;
    }
    printf("%dn", ans);
    return 0;
}

输入

5 3
7 2 1 6 5
3
21
30

输出

YES
YES
NO

说明
对于第一个询问，可以执行一次筛选操作：avg=4,抛弃大于avg的橘子，剩下的橘子为 2 1 恰好和为3，输出YES
对于第二个询问，可以执行零次筛选操作，和为7+2+1+6+5=21，输出YES
对于第三个询问，显然无法办到，所以输出NO

备注:
每次询问是独立的，也就是要从初始状态开始“筛选”

思路：
直接深搜，然后用map保存s可能的值即可，最后q次查询s是否存在。

#include
using namespace std;
using LL = long long;
struct Orange
{
    LL sum = 0;
    vectorv;
}orange;
int n, q, a;
LL s;
mapmp;
void dfs(Orange ora) {
    mp[ora.sum]++;
    if(ora.v.size() == 1) return;
    int avg = ora.sum / ora.v.size();
    Orange Max, Min;
    for(auto &i:ora.v) {
        if(i > avg) {
            Max.sum += i;
            Max.v.push_back(i);
        } else {
            Min.sum += i;
            Min.v.push_back(i);
        }
    }
    ora.v.clear();
    if(Min.v.size() == 0 || Max.v.size() == 0) return;
    dfs(Max);
    dfs(Min);
}
int main() {
    scanf("%d%d", &n, &q);
    for(int i = 0; i < n; i++) {
        scanf("%d", &a);
        orange.sum += a;
        orange.v.push_back(a);
    }
    dfs(orange);
    while(q--) {
        scanf("%d", &s);
        if(mp.count(s)) puts("YES");
        else puts("NO");
    }
    return 0;
}

思路：
找同一数字出现最多的次数就可以

#include
using namespace std;
int main() {
    int n, x;
    scanf("%d", &n);
    mapmp;
    for(int i = 0; i < n; i++){
        scanf("%d", &x);
        mp[x]++;
    }
    int ans = 0;
    for(auto &i:mp) {
        ans = max(ans, i.second);
    }
    printf("%d", ans);
    return 0;
}