贝壳秋招笔试四道编程题（2021-09-03）

古城微笑少年丶 2022-09-10 03:16 251阅读 0赞

> 通知：**华为**、**贝壳**最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在微信公众号【TechGuide】了，公众号回复【华为】或者【贝壳】即可获得最实时、最详细的笔试题解啦！

### 文章目录 ###

*  第一道：木棒长度（100%）
 *   *  题目描述
     *  参考代码：
 *  第二道：括号匹配（100%）
 *   *  题目描述
     *  参考代码
 *  第三道： 最大价值（70%）
 *   *  题目描述
     *  参考代码
     *   *  CPP版本（100%）
         *  Python版本
         *  Java版本（70%）
 *  第四道：（待补充）

# 第一道：木棒长度（100%） #

## 题目描述 ##

牛牛拥有n根木棒，长度分别为1.2…n。

现在，牛牛可以做若干次操作，每一次操作，可以选择任意两根木棒，将它们拼接在起，假设选择的两根木棒的长度分别为 a 和 b，那么拼接后的木棒长度为 a + b。那么，在停止操作之后，牛牛最多可以得到几根长度相同的木棒?

**输入描述**  
本题为多组测试数据，第一行输人一个正整数T(1<T<10^5)，代表测试数据的组数。  
接下去T行，每行一个正整数 n (1≤n≤10^5)，代表木棒的数量，同时表明，木棒的长度分别为1.2…n

**输出描述**  
对于每组测试数据，一行输出一个整数代表答案。

## 参考代码： ##

import sys
    t = int(sys.stdin.readline().strip())
    for index in range(t):
        n = int(sys.stdin.readline().strip())
        if n==1 or n==2:
            print(1)
        else:
            if n%2==1:
                print(n//2+1)
            else:
                print(n/2) 
    # 关注TechGuide！ 大厂笔经面经闪电速递！

# 第二道：括号匹配（100%） #

## 题目描述 ##

输入一串由括号“(”、“)”构成的括号序列，计算不成对的括号对数，比如 “)(())(” 有两对匹配括号，不匹配括号对数为1。

**输入描述**  
t表示测试用例组数，n表示括号序列长度，s表示括号序列

**输出描述**  
ans表示不匹配括号对数

## 参考代码 ##

#include<bits/stdc++.h>
     using namespace std; 
     int main(){ 
     int mid=0,t=0,n=0;
     string s;
     cin>>t;
     for (int i = 0; i < t; ++i) { 
      cin>>n;
      cin>>s;
      int ans=0;
      mid=0;
      for (int j = 0; j < n; ++j) { 
       if (s[j]==')'){ 
        mid++;
        if (mid>0){ 
         ans++;
         mid--;
        }
       }else{ 
        mid--;
       }
      }
      cout<<ans<<'\n';
     }
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第三道： 最大价值（70%） #

## 题目描述 ##

共有n件物品，每件物品价值为w\[i\]。你共有n次机会，每次可以拿一件物品，但如果你第i次拿的物品价值超过m(严格大于)，则后续的第\[i+1,i+k\]次机会将作废,从第 i+k+1 次开始才可以继续拿物品。你每次可以拿任意一件物品，现在想知道在此规则下，你能拿到的物品总价值最大是多少?

**输入描述**  
第一行三个正整数，物品数和机会数n，后续作废k次，价值阈值m;  
第二行n个正整数，每件物品的价值w\[i\]。

5 2 10
    5 8 10 15 33

**输出描述**  
一个正整数，表示拿到的物品最大总价值。

## 参考代码 ##

### CPP版本（100%） ###

第三题分组，大于阈值的放一个数组里，小于等于阈值的放一个数组里，排序后取小数组的k+1个元素和大数组的最大的那个元素比较，谁大取谁，取完后别忘记n-对应次数。

int main(){ 
        int n, k, m;
        cin >> n >> k >> m;
        vector<int> a(n, 0);
        for (int i = 0; i < n; i++)
        { 
            cin >> a[i];
        }
        sort(a.begin(), a.end()); //排序
        vector<ll> pre(n + 1, 0);
        for (int i = 1; i <= n; i++)//n个位置前缀和数组
        { 
            pre[i] = a[i - 1] + pre[i - 1];
        }
        if (k >= n - 1 || a[0] > m)//只能选一个数，选最大的
        { 
            cout << a[n - 1];
            return 0;
        }
        if (a[n - 1] <= m)//可以选全部数
        { 
            cout << pre[n];
            return 0;
        }
        vector<int>::iterator it = upper_bound(a.begin(), a.end(), m);
        int index = distance(a.begin(), it);
        ll res = pre[index];//在数组a中找到大于m的第一个数的下标index，则至少能选择index前的所有数
        for (int i = 1; i <= n - index; i++)//大于m的数共有n-index个，枚举共能选多少个大于m
        { 
            ll t = pre[n] - pre[n - i];//选取i个最大的
            if (n - i - k * (i - 1) >= 0)//选择i个最大的，则至少去掉i+k*（i-1）个数,考虑剩下的个数（此时应取的是小于m的数），从index处往前取剩下的个数
            { 
                t += pre[index] - pre[max(index - (n - i - k * (i - 1)),0)];
            }
            else 
                break;
            res = max(res, t);
        }
        cout << res << '\n';
    }

### Python版本 ###

n, k, m = map(int, input().strip().split())
    value = list(map(int, input().strip().split()))
    # 大组
    value1 = [x for x in value if x>10]
    # 小组
    value2 = [x for x in value if x<=10]
    # 大到小 排序
    value1.sort(reverse=True)
    value2.sort(reverse=True)
    res = 0
    def pick1():
        global res,n
        res += value1[0]
        value1.pop(0)
        n -= (k + 1)
    def pick2():
        global res,n
        res += value2[0]
        value2.pop(0)
        n -= 1
    while n>0:
        # 小组为空，只能取大组
        if(len(value2)==0):
            pick1()
            continue
        # 大组为空，只能取小组
        if (len(value1) == 0):
            pick2()
            continue
        # 都不为空
        # 取了大组就会结束的情况，仅在最后一次机会取大组元素
        if n<=k+1:
            if n == 1:
                pick1()
            else:
                pick2()
        # 取了大组仍不会结束的情况
        # 进行value1[0]和sum(value2[0:3])的比较
        else:
            if sum(value2[0:3])<value1[0]:
                pick1()
            else:
                pick2()
    print(res)
    # 关注TechGuide！ 大厂笔经面经闪电速递！

### Java版本（70%） ###

先排序，每次比较倒数第二个数max2与前面k个小于（等于漏了）m的数的和（记为add），如过max2<add，则添加前面前k个<=m的数和add，并从列表中移除，如果max2>add（等于忘记判断了）,则把最后一个数加到结果中，并且删除前k个数和最后一个数，直到列表长度<=k或者列表倒数第二个数小于m都可以结束循环，再去处理剩下的元素。

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.Scanner;
    
    public class Test03 { 
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt() ;
            long k=sc.nextLong();
            int m=sc.nextInt();
            long[] w = new long[n];
            for (int i = 0; i < n; i++) { 
                w[i] = sc.nextLong();
            }
            System.out.println(solve(w,n,k,m));
        }
    
        private static long solve(long[] w, int n, long k, int m) { 
            Arrays.sort(w);
            List<Long> list = new ArrayList<>();
            for (int i = 0; i < n; i++) { 
                list.add(w[i]);
            }
            if(k == 0 || list.get(list.size()-2) <= m) { 
                return addOfList(list);
            }
            long ans = 0;
            while(list.size() >(k+1) && list.get(list.size()-2)>m){ 
                long max = list.get(list.size()-2);
                long kAdd = 0;
                for(int i=0;i<k;i++){ 
                    if(list.get(i) < m) kAdd += list.get(i);
                }
                if(kAdd > max){ 
                    ans = ans + kAdd;
                    for(int i=0;i<k;i++){ 
                        if(list.get(0) < m) list.remove(0);
                    }
                }else{ 
                    ans+=list.get(list.size()-1);
                    list.remove(list.size()-1);
                    for(int i=0;i<k;i++){ 
                        list.remove(0);
                    }
                }
            }
            if(list.size() > (k+1)){ 
                return ans + addOfList(list);
            }
            for(long num : list){ 
                if(num <= m) { 
                    ans+=num;
                }
            }
            if(list.get(list.size()-1) > m){ 
                ans+=list.get(list.size()-1);
            }
            return ans;
        }
    
        public static long addOfList(List<Long> list){ 
            long ans = 0;
            for(long num : list){ 
                ans+=num;
            }
            return ans;
        }
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第四道：（待补充） #

> 恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。