Day1 组队竞赛、删除公共字符

北海

发布于 2023-07-01 14:03:46

2260

选择题

1.C基础语法

题目：以下程序的运行结果是（）

#include <stdio.h>
int main(void) 
{
	printf("%s , %5.3s\n", "computer", "computer");
	return 0;
}

选项：

A. computer , puter
B. computer , com
C. computer , computer
D. computer , compu.ter

分析：本题知识点为 printf 打印格式控制，其中 %s 为打印字符串，而数字可以控制格式长度：其中 . 前的数字表示打印时缩进 N 个空格，而 . 后的数字表示取目标前 M 位字符

关于其他输出格式

第一个 %s 在打印时，表示直接将 computer 打印完，而第二个 %s 表示先缩进 5 个空格，在取 computer 的前 3 个字符打印，剩余字符不再打印

注意： 当 . 后面的数字大于目标字符串长度时，直接打印整个字符串

结果：B

编程题

1.组队竞赛

题目链接：组队竞赛

题目分析：输入 N 组队伍信息（一个队伍固定为 3 人），规定队伍中的第二名队员（第二大的值）的水平为该队的水平值，尽可能将队员进行合理组队，确保总的队伍水平值为最大

如何确保平均水平值为最大？在组队时，将当前队员中的 最高、次高 和 最低 组成一个队，直到所有的队员都被选中，此时问题就很简单了，关键点在于排序
输入的数据可能为乱序，因此需要先排序，方便进行队员选取
假设当前队员还剩余 N 个，那么此时只需要将 max += N - 1，取得当前队伍的水平值，再 N -= 2，将已经匹配完的队员数去掉，如此重复，直到所有队员都被选中

代码时间复杂度：3n + (3n)*log(3n) + n -> O(N*logN) 空间复杂度：O(3n)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n = 0;
    while (cin >> n)
    {
        vector<int> member(n * 3);  //成员池
        for (int i = 0; i < n * 3; i++)
            cin >> member[i];   //读取成员值

        sort(member.begin(), member.end()); //排序
        int pos = 0;
        int N = member.size() - 1;

        long long max = 0;  //注意：存在溢出的情况

        while (pos < N)
        {
            max += member[N - 1];
            pos++;
            N -= 2;
        }

        cout << max << endl;
    }
	return 0;
}

注意：

输入的 n 为队伍数，实际队员数为 3 * n
获取队员水平后，需要对数值进行排序，否则无法进行后续计算
存在溢出问题，因此 max 需要一个更大的类型

结果

2.删除公共字符

题目链接：删除公共字符

题目分析：将 字符串1 中所有在 字符串2 中出现的字符删除，本质：删除公共字符

思路1：先 字符串2 遍历，然后将遍历得到的值，带到 字符串1 中再去遍历，如果发现相同的，就删除
思路2：重构字符串，将 字符串2 构建为 map，对 字符串1 进行遍历，如果该字符已出现在 map 中，那么就不参与重构

两种思路各有优劣，思路1耗时间（重复遍历+删除），而思路2耗费空间，并且是间接到达删除的要求

思路1

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

//思路1
int main()
{
    string str1, str2;

    //需要使用 getline 因为输入字符串有空格
    getline(cin, str1);
    getline(cin, str2);

    //先将 str2 遍历一遍
    for (auto e : str2)
    {
        int val = e;
        auto it = str1.begin();

        //再将 str1 遍历，将需要删除的字符移除
        while (it != str1.end())
        {
            //注意迭代器失效问题
            if (*it == val)
                it = str1.erase(it);    //删除字符
            else
                it++;
        }
    }

    cout << str1 << endl;

    return 0;
}

思路2

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

//思路2
int main()
{
    string str1, str2;

    //需要使用 getline 因为输入字符串有空格
    getline(cin, str1);
    getline(cin, str2);

    //建立 map 表，表示是否出现
    map<char, int> table;
    for (auto e : str2) table.insert(make_pair(e, 1));

    //将 str1 遍历，重构字符串
    string tmp;
    for (auto e : str1)
    {
        if (table.find(e) == table.end())
            tmp += e;   //只有未出现的，才能记录
    }

    str1 = tmp;

    cout << str1 << endl;

    return 0;
}