笔试强训每日一题

组队竞赛

题目描述

牛牛举办了一次编程比赛,参加比赛的有3*n个选手，每个选手都有一个水平值a_i.现在要将这些选手进行组队，一共组成n个队伍,即每个队伍3人，牛牛发现队伍的水平值等于该队伍队员中第二高水平值。
例如:
一个队伍三个队员的水平值分别是3,3,3.那么队伍的水平值是3一个队伍三个队员的水平值分别是3,2,3.那么队伍的水平值是3一个队伍三个队员的水平值分别是1.5.2.那么队伍的水平值是2，为了让比赛更有看点，牛牛想安排队伍使所有队伍的水平值总和最大。

如样例所示:
如果牛牛把6个队员划分到两个队伍如果方案为:
team1:{1,2,5)，team2:{5,5,8}，这时候水平值总和为7，而如果方案为:
team1:{2.5.8]，team2:{1.5.5)。这时候水平值总和为10，没有比总和为10更大的方案，所以输出10。

这是怎么分组的问题，队伍的水平值等于该队伍队员中第二高水平值，为了所有队伍的水平值总和最大的解法，也就是说每个队伍的第二个值是尽可能大的值。所以实际值把最大值放到最右边，最小是放到最左边。

解题思路

本题的主要思路是贪心算法，每次选值时都选当前能看到的局部最解忧，所以这里的贪心就是保证每组的第二个值取到能选择的最大值就可以，我们每次尽量取最大，但是最大的数不可能是中位数，我们需要取每组中第二大的，我们首先对数组排序，排序后有1 2 5 5 8 9，每次分组，选最小的一个和最大的两个，那么分组为1 8 9和2 5 5，每组选出的值的下标为：arr[arr.length-2*(i+1)]

解题代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    long long sum = 0;
    int n;
    cin>>n;
    vector<int> v;
    v.resize(3*n);
    for(int i =0 ;i<3*n;i++)
    {
        cin>>v[i];
    }
    std::sort(a.begin(),a.end());
    for(int i = 0;i < n;i++)
    {
        sum = sum+v[v.size()-2*(i+1)];
    }
    cout<<sum<<endl;
}

分配饼干问题

题目描述

有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃
最多一个饼干，且只有饼干的大小大于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。

输入输出样例：
输入两个数组，分别代表孩子的饥饿度和饼干的大小。输出最多有多少孩子可以吃饱的数
量。
Input: [1,2], [1,2,3]
Output: 2

解题思路

因为饥饿度最小的孩子最容易吃饱，所以我们优先分配饥饿度小的孩子，为了使得剩下的饼干的大小能够更大，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。所以我们给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干

解题代码

int findContentChildren(vector<int>& children, vector<int>& cookies)
{
    //首先排序
    sort(children.begin(),children.end());
    sort(cookies.begin(),cookies.end());
    int child = 0;
    int cookie = 0;
    while(child<children.size() && cookie < cookies.size())
    {
        if(children[child] <= cookies[cookie])
        {
            //孩子的饥饿度最小的和饼干大小最小的，如果能吃饱孩子
            child++;
        }
        cookie++;
    }
}

在字符串中删除特定的字符

题目描述

输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入 ”They arestudents.” 和 ”aeiou” ，则删除之后的第一个字符串变成 ”Thy r stdnts.”

解题思路

1.将第二个字符串的字符都映射到一个count数组中，用来判断一个字符在这个字符串。

2.判断一个字符在第二个字符串，不要使用删除，这样效率太低，因为每次删除都伴随数据挪动。这里可以考虑使用将不在字符添加到一个新字符串，最后返回新新字符串。

解题代码

#include<iostream>
#include<string>
using namespace std;
int main()
{
    string str1,str2;
    getline(cin,str1);
    getline(cin,str2);
    //使用哈希映射思想先统计要删除的字符
    int count[256] = {0};
    for(size_t i = 0;i<str2.size();i++)
    {
        count[str2[i]]++;
    }
    //遍历str1，str1[i]映射count对应位置为0，则表示这个字符在str2中没有出现过
    string ret;
    for(size_t i = 0;i<str1.size();i++)
    {
        if(count[str1[i]]==0)
        {
            ret += str1[i];
        }
    }
    cout<<ret<<endl;
    return 0;
}