【编程强训】删除公共字符（哈希映射）+组队竞赛（贪心）

1.删除公共字符 ->链接

【解题思路】：

本题如果使用传统的暴力查找方式，如判断第一个串的字符是否在第二个串中，在再挪动字符删除这个字符
的方式，效率为O(N^2)，效率太低，很难让人满意。

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

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

实现代码：

#include<iostream>
#include<string>
using namespace std;

int main()
{
    
    string s1,s2;
    // 注意这里不能使用cin接收，因为cin遇到空格就结束了。
    // oj中IO输入字符串最好使用getline。
    getline(cin,s1);
    getline(cin,s2);
    
    int hash[256]={
    0};
    // 使用哈希映射思想先str2统计字符出现的次数
    for(int i=0;i<s2.size();i++)
    {
    
        hash[s2[i]]++;
    }
    
    // 遍历str1，str1[i]映射hashtable对应位置为0，则表示这个字符在 
    // str2中没有出现过，则将他+=到ret。注意这里最好不要str1.erases(i) 
    // 因为边遍历，边erase，容易出错。
    string ret="";
    for(int j=0;j<s1.size();j++)
    {
    
        if(hash[s1[j]]==0)
            ret+=s1[j];
    }
    
    cout<<ret<<endl;
    return 0;
    
}

2.组队竞赛 -> 链接

【题目解析】：

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

【解题思路】：

本题的主要思路是贪心算法，贪心算法其实很简单，就是每次选值时都选当前能看到的局部最解忧，所以这里的贪心就是保证每组的第二个值取到能选择的最大值就可以，我们每次尽量取最大，但是最大的 数不可能是中位数，所以退而求其次，取每组中第二大的。

• 例如 现在排序后 有 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()
{
    
    int n=0;
   //循环实现多组测试
    while(cin>>n)
    {
    
         vector<int> a;
        long long sum=0;
        a.resize(3*n);
        for(int i=0;i<3*n;i++)
        {
    
            cin>>a[i];
        }
        std::sort(a.begin(),a.end());//用sort实现升序排序
        for(int i=0;i<n;i++)
        {
    
            sum+=a[a.size()-(2*(i+1))];
        }
      cout<<sum<<endl;
    }
   
    return 0;
}