C++日常刷题积累

• 今日刷题汇总 - day014
• • 1、乒乓球筐
  • • 1.1、题目
    • 1.2、思路
    • 1.3、程序实现
  • 2、组队竞赛
  • • 2.1、题目
    • 2.2、思路
    • 2.3、程序实现
  • 3、删除相邻数字的最大分数
  • • 3.1、题目
    • 3.2、思路
    • 3.3、程序实现 -- dp+hash
  • 4、题目链接

今日刷题汇总 - day014

1、乒乓球筐

1.1、题目

1.2、思路

读完题知道，需要判定A、B两盒乒乓球中，A是否包含了B中所有类型的乒乓球，其中类型以大写字母表示。如果B盒中所有球的类型在A中都有，并且每种球的数量都不大于A，则输出“Yes”；否则输出“No”即可。其实这道题本质就是两个字符串，A串包括了B串中所有字符，那么想到可以利用hash表的思路解决，因为还得考虑字符的数量问题，满足B中g该球的数量不大于A中该球的数量。然后思路步骤就出来了：
(1)、利用哈希映射，统计A字符串中字符的频次；
(2)、再遍历利用哈希，减去B字符串出现的字符；
(3)、最后再次利用哈希查询数目是否满足题目要求，即查看哈希表中B中对应字符下标的数量是否小于0，小于说明，A中对应B的字符数量不足或者不存在B的字符。否则，输出“yes”.

1.3、程序实现

首先按照题目要求，完成多组输入，定义所需的int型hash表，方便统计数量，根据思路完成三个for循环遍历即可。值得注意的是这里可以使用标志位，区分输出结果。

#include  #include  using namespace std;  int main() {     string A, B;     while (cin >> A >> B)     {         int hash[26] = { 0 };         for (int i = 0; i < A.size(); i++)         {             hash[A[i] - 'A']++;         }         int flag = 1;         for (int i = 0; i < B.size(); i++)         {             hash[B[i] - 'A']--;         }         for (int i = 0; i < B.size(); i++)         {             if (hash[B[i] - 'A'] < 0)             {                 flag = 0;                 break;             }         }         cout << (flag ? "Yes" : "No") << endl;     }     return 0; } 

由于后两个循环都是对B进行判断操作，所以可以结合写在一起。

#include  #include  using namespace std;  int main() {     string A, B;     while (cin >> A >> B)     {         int hash[26] = { 0 };         for (int i = 0; i < A.size(); i++)         {             hash[A[i] - 'A']++;         }         int flag = 1;         for (int i = 0; i < B.size(); i++)         {             if (--hash[B[i] - 'A'] < 0)             {                 flag = 0;                 break;             }         }         cout << (flag ? "Yes" : "No") << endl;     }     return 0; } 

其次，也可以用范围for执行遍历的逻辑。

#include  #include  using namespace std;  int main() {     string A, B;     while (cin >> A >> B)     {         int hash[26] = { 0 };         for (auto ch1 : A)         {             hash[ch1 - 'A']++;         }         int flag = 1;         for (auto ch2 : B)         {             if (--hash[ch2 - 'A'] < 0)             {                 flag = 0;                 break;             }         }         cout << (flag ? "Yes" : "No") << endl;     }     return 0; } 

2、组队竞赛

2.1、题目

2.2、思路

读完题，知道让实现所有比赛组合的水平值最大，其中，每个队伍的水平值有该队伍第二高的选手水平值决定。那么，思路想到贪心法，尽可能让每个队伍都分到的第二高水平值的选手水平值高且接近，那么我们可以将每个选手的水平值进行sort排序，如5，2，8，5，1，5 排序后得到，1，2，5，5，5，8，此时组队要水平值和最大，就把最大值放一组的最后，次大值作为该组第二个位置，再次大值作为第二组最大值，再将下一个值作为第二组的第二个位置，这样组成才是最大水平的和，所以最后我们就只需要拿去每一组第二个位置的值即可。为了直观的观察，画个图理解推导过程：

那么接下来，就是程序实现。

2.3、程序实现

首先。按照题目要求写好输入部分，接着就是排序数组，目的是方遍索引每组次高位的下标位置，然后就定义index每组次高位的下标，然后定义retmaxsum 最大水平值，然后将每组的次高位累计加即可。主要是能想到第二位之间的下标关系就很好处理了。

#include  #include  using namespace std;  const int N = 1e5 + 10; long long arr[N*3];  int main() {     int n;     cin >> n;     for(int i = 0;i < n*3;i++)         cin >> arr[i];     sort(arr,arr+ 3*n);     int index = 3*n - 2;     long long retmaxsum = 0;     while(n--)     {         retmaxsum += arr[index];         index -= 2;     }     cout << retmax << endl;     return 0; } 

3、删除相邻数字的最大分数

3.1、题目

3.2、思路

读完题，知道让在一组数组中选择任意一个元素ai，获取它的数值作为分数，同时然后去掉数组中ai-1和ai+1的元素，最终知道所有元素都被去除或者获取，要求得到最后的分数最大。那么，根据示例和题目规则分析，为了方便理解画个图：

那么接下来，就是程序实现。

3.3、程序实现 – dp+hash

首先，按照题目需要写好输入，再根据思路分析，只要分为以下几个步骤即可：
(1)、预处理数组元素，转成hash表下标索引统计每个元素的分数值；
(2)、遍历统计好对应元素分数的哈希数组，执行状态转移方程；
(3)、输出f[i]和g[i]这两种情况的最大值即可
值得注意的是，这里转换成hash的数组执行逻辑，所以遍历时遍历hash数组N的范围

#include  using namespace std;  const int N = 1e4 + 10;  int hashcount[N] = { 0 };  int f[N]; int g[N];  int main() {     int n;     cin >> n;     int a = 0;     for(int i = 0;i < n;i++)     {         cin >> a;         hashcount[a] += a;//统计a元素的分值和     }     //遍历哈希表     f[0] = g[0] = 0;     for(int i = 1;i < N;i++)     {         f[i] = hashcount[i] + g[i-1];         g[i] = max(f[i-1],g[i-1]);     }     //输出这两种情况的最大值即可     cout << max(f[N-1],g[N-1]) << endl;     return 0; } 

4、题目链接

🌟乒乓球筐
🌟组队竞赛
🌟删除相邻数字的最大分数