文章目录

• 第一题：最小的 k 个数
• • 题目描述
  • 输入格式
  • 输出格式
  • 输入样例
  • 输出样例
  • 解题思路&C++题解
  • • 算法
• 第二题：智慧之海
• • 故事背景
  • 题目描述
  • 输入格式
  • 输出格式
  • 输入样例
  • 输出样例
  • 解题思路&C++题解

网站设计制作过程拒绝使用模板建站；使用PHP+MYSQL原生开发可交付网站源代码;符合网站优化排名的后台管理系统；成都网站设计、网站制作收费合理；免费进行网站备案等企业网站建设一条龙服务.我们是一家持续稳定运营了10年的创新互联网站建设公司。第一题：最小的 k 个数 题目描述

有一个长度为 n 的由 0 和 1 组成的字符串 s，你需要用最少的步数将其变成只包含 0 的字符串。在每一步中，你可以选择任意一个子串，并将其中所有 1 都反转为 0。你需要输出最少的步数。

例如，对于字符串 s = “110101”，你可以进行如下步骤：

第一步：反转从第 1 个字符到第 3 个字符的子串 “110”，得到字符串 “000101”。
第二步：反转从第 1 个字符到第 6 个字符的子串 “000101”，得到字符串 “000000”。
因此，最少的步数为 2。

输入格式

输入的第一行包含一个字符串 s，长度不超过 1 0 5 10^5 105。

输出格式

输出一个整数，表示最少的步数。

输入样例

110101

输出样例

2

解题思路&C++题解

请在下面编写你的 C++ 代码来解决这道题目：

#include#includeusing namespace std;

int main() {// 读入字符串 s
  string s;
  cin >>s;

  // 计算最少的步数
  int steps = 0;
  // 在此处编写你的代码

  // 输出结果
  cout<< steps<< endl;

  return 0;
}

算法

这道题目的算法设计是使用前缀和数组来计算最少的步数。

首先，我们从前往后遍历字符串 s，并计算出前缀和数组 prefix。前缀和数组的定义是，对于字符串 s，前缀和数组为 a，则 a[i] 表示 s[1] 到 s[i] 中 1 的数量。

然后，对于每一个字符，我们进行如下操作：

如果当前字符是 1，则将步数加 1。
否则，枚举以当前字符为起点的子串，并计算出它中 1 的数量。然后用这个数量来更新答案。
这样的时间复杂度是 O ( n 2 ) O(n^2) O(n2)，因为我们对于每一个字符都枚举了它的子串。

但是，我们可以使用前缀和数组来优化这个算法。使用前缀和数组，我们可以在 O ( 1 ) O(1) O(1)的时间内计算出任意一个子串中 1 的数量。因此，我们可以将时间复杂度优化到 O ( n ) O(n) O(n)。

下面是 c++ 代码实现：

#include#includeusing namespace std;

int main() {// 读入字符串 s
  string s;
  cin >>s;
  int n = s.size();

  // 计算前缀和数组
  int prefix[n + 1];
  prefix[0] = 0;
  for (int i = 1; i<= n; i++) {prefix[i] = prefix[i - 1] + (s[i - 1] == '1');
  }

  // 计算最少的步数
  int steps = 0;
  for (int i = 0; i< n; i++) {// 如果当前字符是 1，则将步数加 1
    if (s[i] == '1') {  steps++;
    }
    // 否则，枚举以当前字符为起点的子串
    else {  for (int j = i + 1; j<= n; j++) {// 计算子串中 1 的数量
        int ones = prefix[j] - prefix[i];
        // 更新答案
        steps = min(steps, ones);
      }
    }
  }

  // 输出结果
  cout<< steps<< endl;

  return 0;
}

上面的代码实现了状态转移方程的过程。

注意：

• 矩阵的行和列都是从 1 开始编号的，所以要注意初始化和转移的时候数组下标的边界。

• 在转移的时候，需要考虑使用道具的情况。

第二题：智慧之海 故事背景

海神波塞冬拥有着神奇的能力，他能够将一个人的智慧转化成数字，并将这个数字存储在一个无序数组中。但是，有一天，海神波塞冬收到了一个神秘的任务，要求他从这个无序数组中找出最小的 k 个数，并将它们存储在另一个数组中。

题目描述

给定一个无序数组 a 和整数 k，你需要在 a 中找出最小的 k 个数，并将它们存储在另一个数组 b 中。

例如，对于数组 [3, 4, 1, 2, 5] 和 k = 3，你可以进行如下操作：

第一步：找出数组中最小的数字 1，将其存储在另一个数组 b 中。
第二步：找出数组中第二小的数字 2，将其存储在另一个数组 b 中。
第三步：找出数组中第三小的数字 3，将其存储在另一个数组 b 中。
因此，最后得到的另一个数组 b 为 [1, 2, 3]。

请在下面编写你的 C++ 代码来解决这道题目：

#include#include 

using namespace std;

int main() {// 读入数组 a 和 k
  int a[10], k;
  for (int i = 0; i< 10; i++) {cin >>a[i];
  }
  cin >>k;

  // 计算最小的 k 个数并存储在另一个数组 b 中
  int b[k];
  // 在此处编写你的代码

  // 输出结果
  for (int i = 0; i< k; i++) {cout<< b[i]<< " ";
  }
  cout<< endl;

  return 0;
}

请注意，你的算法的时间复杂度应该尽可能低。

输入格式

第一行包含整数 n，表示数组 a 的长度。

第二行包含 n 个整数，依次为数组 a 的元素。

第三行包含整数 k。

输出格式

输出一行，包含 k 个整数，依次为数组 b 中的元素。

输入样例

5
3 4 1 2 5
3

输出样例

1 2 3

解题思路&C++题解

这道题的题意是，给定一个无序数组 a 和整数 k，你需要在 a 中找出最小的 k 个数，并将它们存储在另一个数组 b 中。

解题思路：

一种方法是使用排序算法将数组 a 排序，然后直接取前 k 个数即可。时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。

另一种方法是使用堆来解决这道题。我们可以将数组 a 中的数字插入到一个大根堆中，然后每次取出堆顶元素，将其存储在数组 b 中。这样，当我们取出了 k 个数字之后，堆中剩余的数字就是最小的 k 个数字。因此，我们可以在每次插入元素之前检查堆的大小，如果堆的大小超过 k，就将堆顶元素弹出。

这种方法的时间复杂度为 O ( n l o g k ) O(nlogk) O(nlogk)，要比前一种方法更优。

下面是使用堆来解决这道题的 C++ 代码：

#include#include 
#includeusing namespace std;

int main() {// 读入数组 a 和 k
  int n, k;
  cin >>n;
  int a[n];
  for (int i = 0; i< n; i++) {cin >>a[i];
  }
  cin >>k;

  // 计算最小的 k 个数并存储在另一个数组 b 中
  int b[k];
  priority_queue, greater>q;
  for (int i = 0; i< n; i++) {q.push(a[i]);
    if (q.size() >k) {  q.pop();
    }
  }
  for (int i = k - 1; i >= 0; i--) {b[i] = q.top();
    q.pop();
  }

  // 输出结果
  for (int i = 0; i< k; i++) {cout<< b[i]<< " ";
  }
  cout<< endl;

  return 0;
}

这就是使用堆来解决本题的解法。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文名称：每日一练c++题目日刊|第七期-创新互联
文章源于：http://kswjz.com/article/djsgce.html