文章目录
- 1.多组输入计算a+b
- 2.给定组数计算a+b
- 3.给定组数计算a+b(如果为0则结束)
- 4.计算一些列数的和(第一个数为0时结束)
- 5.计算一些列数的和(告诉了有几组)
- 6.计算一系列数的和(不告知几组和何时结束,每一组第一个数为一共本组几个数)
- 7.计算一系列数的和(一行一组,不告诉一组几个,需要判断)
- 8.字符串排序(只排一组,告诉有几个)
- 9字符串排序(无固定组数)
- 10.字符串排序(输入用逗号分开)
- 11.注意数据范围,用 long
- 这道题想要教会我们什么?
- stringstream详解
- sort详解
- 1. 函数原型
- 2. 排序的时间复杂度
- 3. 使用场景
- 4. 常见用法
- 4.1. 对数组进行排序
- 4.2. 对 **`std::vector`** 进行排序
- 4.3. 自定义排序规则
- 4.4. 对结构体进行排序
- 4.5. 部分排序
- 4.6 使用比较函数对象
- 4.6.1 `greater<int>`函数对象
- 4.6.2 其他常见的函数对象
- 4.6.3 自定义函数对象
- 5. 注意事项
- 6. 总结
本篇文章将详细介绍在ACM模式下常见的输入输出类型,搞懂这11道题可以帮我们打好算法基础,避免因为最后结果的输出导致无法完成题目。在讲完题目之后再讲两个常用的函数:
stringstream
和
sort
。
1.多组输入计算a+b
#include<iostream>
using namespace std;
int main()
{int a,b;//使用while循环来处理所有输入while(cin>>a>>b){cout<<a+b<<endl;}return 0;
}
2.给定组数计算a+b
#include<iostream>
using namespace std;
int main()
{int n;cin>>n;int a,b;while(n--){cin>>a>>b;cout<<a+b<<endl;}return 0;
}
3.给定组数计算a+b(如果为0则结束)
#include<iostream>
using namespace std;
int main()
{int a,b;while(cin>>a>>b){if(a==b&&b==0){break;}cout<<a+b<<endl;}return 0;
}
**while**
** 循环** 更适合处理未知数量的输入数据,使用起来更灵活,也是处理这种"无限输入,特定条件结束"的经典方式。**for**
** 循环** 在你知道确切的循环次数时使用更为方便,但在这个问题中,因为输入可能是无限的,因此while
循环会更常用和合适。
4.计算一些列数的和(第一个数为0时结束)
解法1:
#include<iostream>
using namespace std;int main() {int n;while (cin >> n && n != 0) { // 读取整数个数n,且n不为0时进入循环int sum = 0, temp;for (int i = 0; i < n; i++) { // 循环读取n个整数并求和cin >> temp;sum += temp;}cout << sum << endl; // 输出求和结果}return 0;
}
解法2:
#include<bits/stdc++.h>
using namespace std;
int main()
{int n=0;while(cin>>n&&n!=0){int sum=0;vector<int> arr(n);for(int i=0;i<n;i++){cin>>arr[i];sum+=arr[i];}cout << sum << endl;}
}
5.计算一些列数的和(告诉了有几组)
#include<iostream>
using namespace std;
int main() {int t;cin >> t; // 读取数据组数while (t--) { // 当t > 0时循环,每次循环处理一组数据int n, sum = 0;cin >> n; // 读取当前组的整数个数for (int i = 0; i < n; i++) { // 循环读取n个正整数并求和int temp;cin >> temp;sum += temp;}cout << sum << endl; // 输出当前组的和}return 0;
}
6.计算一系列数的和(不告知几组和何时结束,每一组第一个数为一共本组几个数)
#include<iostream>
using namespace std;
int main() {int n;while(cin >> n) { // 逐行读取每行的第一个整数,即整数的个数int sum = 0;for(int i = 0; i < n; i++) {int num;cin >> num; // 逐个读取正整数sum += num; // 将其加入求和变量}cout << sum << endl; // 输出该行的和}return 0;
}
7.计算一系列数的和(一行一组,不告诉一组几个,需要判断)
解法1:
#include <iostream>
using namespace std;
int main() {int sum = 0;int a;while (cin >> a) {sum += a;// 这里用 cin.get() 是换行符来判断,是否到了最后一个数,如果是的话,就把和输出出来,并把 sum 置零if (cin.get() == '\n') {cout << sum << endl;sum = 0; // 清零以准备下一行}}
}
解法2:
#include <iostream>
using namespace std;
int main() {int a;int sum = 0;while (scanf("%d", &a) != EOF) {sum += a;if (getchar() == '\n') {printf("%d\n", sum);sum = 0; // 清零以准备下一行}}
}
解法3:
string line; // 定义一个字符串变量line,用于存储一行输入while (getline(cin, line)) // 循环读取每一行输入{stringstream ss; // 创建一个stringstream对象ssss << line; // 将当前行的输入字符串line放入ss中int cur_sum = 0; // 初始化当前行的和cur_sum为0int x; // 定义一个整数变量x,用于存储从ss中读取的每个整数// 从ss中读取整数,直到没有更多的整数可读while (ss >> x)cur_sum += x; // 将读取到的整数累加到cur_sum中cout << cur_sum << endl; // 输出当前行的和}
8.字符串排序(只排一组,告诉有几个)
解法1:
#include<iostream>
#include<vector>
#include<algorithm> // std::sort
using namespace std;int main() {int n;cin >> n;vector<string> strings(n);for(int i = 0; i < n; i++) {cin >> strings[i]; // 读取 n 个字符串}sort(strings.begin(), strings.end()); // 对字符串进行排序//注意末尾没有空格for (int i = 0; i < n - 1; i++){cout << s[i] << " ";}cout << s[n - 1] << endl;return 0;
}
解法2:
int n;vector<string> strs;cin >> n;for (int i = 0; i < n; i++){string str;cin >> str;strs.push_back(str);}sort(strs.begin(), strs.end());for(int i = 0; i < n; i++) {if(i > 0) cout << " "; // 控制输出格式cout << strings[i];}cout << endl;
9字符串排序(无固定组数)
解法1:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {vector<string> words;string word;while (cin >> word) { // 读取每个单词words.push_back(word);if (cin.get() == '\n') { // 检查是否到达行末sort(words.begin(), words.end()); // 对单词进行排序for (size_t i = 0; i < words.size(); ++i) {cout << words[i];if (i < words.size() - 1) {cout << " "; // 输出空格,除非是最后一个单词}}cout << endl; // 换行,处理下一行输入words.clear(); // 清空单词列表,准备下一行输入}}return 0;
}
解法2:
string line; // 用于存储每行输入的字符串while (getline(cin, line)) {stringstream ss(line); // 使用 stringstream 来处理行内的单词vector<string> words; // 存储当前行的所有单词string word; // 临时变量,用于存储每个单词while (ss >> word) {words.push_back(word); // 将提取到的单词存储到 vector 中}sort(words.begin(), words.end()); // 使用标准库中的 sort 函数对单词进行排序for (size_t i = 0; i < words.size() - 1; ++i) {cout << words[i] << " "; // 输出当前单词,并加上空格}cout << words.back(); // 输出最后一个字符串,不带空格cout << endl; // 换行,处理下一行输入
}
10.字符串排序(输入用逗号分开)
解法1:
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>using namespace std;int main() {string line;while (getline(cin, line)) { // 读取一行字符串vector<string> words;string word;stringstream ss(line);while (getline(ss, word, ',')) { // 读取每个单词,使用逗号作为分隔符words.push_back(word);}// 使用 sort 函数对字符串数组进行排序sort(words.begin(), words.end());// 输出排序后的字符串for (size_t i = 0; i < words.size() - 1; i++) {cout << words[i] << ","; // 输出字符串和逗号}cout << words.back(); // 输出最后一个字符串,不带逗号cout << endl;}return 0;
}
11.注意数据范围,用 long
**注意:**看好数据范围
题目要求处理的整数范围是0 < a, b < 2 × 10^10
。然而,int
类型在大多数 C++ 实现中最多只能表示到2^31 - 1
(即大约2.14 × 10^9
),这比题目中的最大值要小得多。使用int
类型来存储输入数据,如果输入的数据非常大,可能会导致整数溢出,进而使结果错误。
正确代码:
#include<bits/stdc++.h>
using namespace std;
int main()
{long long a, b; // 使用 long long 类型以处理更大的数值范围while(cin >> a >> b){cout << (a + b) << endl; // 输出两个大整数的和}return 0;
}
这道题想要教会我们什么?
- 大数处理: 在C++编程中,尤其是在处理大数时,要谨慎选择数据类型。
int
类型在面对超大数值时可能会溢出,因此要熟练掌握使用long long
来处理更大的整数。 - 边界条件测试: 你的代码可能在处理样例和小数据时表现良好,但在面对大范围数据时会暴露问题。这提醒你在设计和测试代码时,需要覆盖更广泛的边界条件。
- 全面的代码测试: 在面对在线编程题时,不仅要在自己的测试环境下测试,还要注意潜在的极限条件。OJ系统通常会有更全面的测试数据,因此提交前要确保代码在所有可能的条件下都能正常运行。
拓展:
long
和long long
long 和 long long 是 C++ 中的两种整数数据类型,它们之间主要的区别在于它们能表示的数值范围不同。
- long 类型
在大多数编译器和平台上,long 通常是 4字节(32位),和 int 一样大。
它的取值范围通常是 -2,147,483,648 到 2,147,483,647,即
2-31到 231 -1
- long long 类型
long long 是一种较新的类型,通常是 8字节(64位),比 long 能表示更大的整数。
它的取值范围通常是 -9,223,372,036,854,775,808 到 9,223,372,036,854,775,807,即
-263到263 -1
stringstream详解
stringstream
是 C++ 标准库中的一个非常有用的类,它结合了字符串操作和流操作的功能。stringstream
允许你像处理文件流一样处理字符串,这在很多场合都非常有用,尤其是在算法题中。下面详细介绍 stringstream
的常见用法和在算法题中的使用场景
当然可以!stringstream
是 C++ 标准库中的一个非常有用的类,它结合了字符串操作和流操作的功能。stringstream
允许你像处理文件流一样处理字符串,这在很多场合都非常有用,尤其是在算法题中。下面详细介绍 stringstream
的常见用法和在算法题中的使用场景。
stringstream 类概述
stringstream
类是 <sstream>
头文件的一部分,它继承自 istream
和 ostream
,这意味着你可以像使用 cin
和 cout
一样使用它来进行输入输出操作。
常见用法
1. 创建 stringstream
对象
#include <sstream>
std::stringstream ss;
2. 向 stringstream
写入数据
你可以使用 <<
运算符向 stringstream
写入数据,就像使用 cout
一样:
ss << "Hello, " << 42 << "!";
3. 从 stringstream
读取数据
你可以使用 >>
运算符从 stringstream
读取数据,就像使用 cin
一样:
int num;
ss >> num; // 读取整数
4. 将 stringstream
转换为字符串
你可以使用 str()
成员函数获取 stringstream
中的内容作为字符串:
std::string str = ss.str();
在算法题中的使用场景
1. 字符串到数字的转换
使用 stringstream
来将字符串转换为数字类型,这对于解析输入非常有用:
#include <iostream>
#include <sstream>
using namespace std;
int main() {string input = "12345";stringstream ss(input);int number;ss >> number;cout << "Number: " << number << endl;return 0;
}
2. 数字到字符串的转换
使用 stringstream
来将数字转换为字符串类型,这对于构建输出非常有用:
#include <iostream>
#include <sstream>using namespace std;int main() {int number = 12345;stringstream ss;ss << number;string strNumber = ss.str();cout << "String: " << strNumber << endl;return 0;
}
3. 字符串分割
使用 getline
和 stringstream
来分割字符串,这对于处理 CSV 或其他分隔符分隔的数据非常有用:
#include <iostream>
#include <sstream>
#include <string>
#include <vector>using namespace std;int main() {string line = "a,c,bb";vector<string> words;string word;stringstream ss(line);while (getline(ss, word, ',')) { // 读取每个单词,使用逗号作为分隔符words.push_back(word);}// 输出排序后的字符串for (size_t i = 0; i < words.size() - 1; i++) {cout << words[i] << ","; // 输出字符串和逗号}cout << words.back(); // 输出最后一个字符串,不带逗号cout << endl;return 0;
}
getline(ss,word,‘,’)
** 在 C++ 中,getline
是一个用于从输入流中读取一行字符串的函数,它也可以从stringstream
这样的流中读取。getline
的第三个参数允许你指定一个分隔符,这样你可以按分隔符来读取数据,而不仅仅是到换行符为止。
**getline(ss, word, ',')**
的含义是从**stringstream**
对象**ss**
中读取字符到字符串**word**
,直到遇到指定的分隔符**,**
为止,或者到达流的结尾。**
下面是这行代码的各个参数的具体含义:
**ss**
: 输入流对象,这里是**stringstream**
。**word**
: 用于存储读取到的字符串。**,**
: 分隔符,表示在读取过程中遇到的逗号**,**
会作为分隔符,读取到逗号时停止读取,逗号不会包括在读取到的字符串中。假设我们有以下的输入流内容
**ss**
,它是一个**stringstream**
对象,内容如下:
apple,banana,orange,grape
以下是几种情况下的
getline(ss, word, ',')
的行为示例:
示例 1代码:
getline(ss, word, ',');
cout << word << endl;
结果:
apple
解释:第一次调用
getline(ss, word, ',')
会读取到第一个逗号,
之前的内容apple
,并将其存储到word
中。然后输出apple
。
示例 2代码:
getline(ss, word, ',');
getline(ss, word, ',');
cout << word << endl;
结果:
banana
解释:第一次调用
getline(ss, word, ',')
会读取apple
。第二次调用getline(ss, word, ',')
会读取banana
,直到下一个逗号,
为止。然后输出banana
。
示例3:代码:
getline(ss, word, ',');
getline(ss, word, ',');
getline(ss, word, ',');
cout << word << endl;
结果:
orange
解释:第一次调用
getline(ss, word, ',')
读取apple
。第二次调用读取banana
。第三次调用读取orange
。此时ss
的下一个内容是grape
。所以word
变为orange
,输出orange
。
示例 4代码:
getline(ss, word, ',');
getline(ss, word, ',');
getline(ss, word, ',');
getline(ss, word, ',');
cout << word << endl;
结果:
grape
解释:前三次调用分别读取
apple
、banana
和orange
。最后一次调用读取到grape
,并且遇到流的结尾,grape
是最后一个单词。输出grape
。
总结:
getline(ss, word, ',')
用于按逗号分隔读取输入流中的字符串,这在处理用特定字符分隔的数据时非常有用。每次调用getline
都会读取到下一个分隔符之前的内容,并将其存储到word
变量中。
4. 读取和写入数据
std::stringstream
结合了 std::istringstream
和 std::ostringstream
的功能,既可以从字符串中读取数据,也可以将数据写入字符串。
示例:读取和写入数据
#include <iostream>
#include <sstream>using namespace std;int main() {stringstream ss; // 创建字符串流ss << "123 456 78.9"; // 将数据写入字符串流int a, b;float c;ss >> a >> b >> c; // 从字符串流中读取数据cout << "a = " << a << endl;cout << "b = " << b << endl;cout << "c = " << c << endl;return 0;
}
在这个例子中,stringstream
同时用作输入和输出流。stringstream
是一个非常强大的工具,它可以帮助你在字符串操作方面更加灵活。它不仅可以在字符串和数字之间进行转换,还可以用于解析和构造字符串,甚至用于模拟文件输入输出。希望这些示例对你有所帮助!如果有任何其他问题,请随时提问。
sort详解
std::sort
是 C++ 标准库中的一个排序算法,用于对容器中的元素进行排序。它位于 <algorithm>
头文件中,并且通常用于对 std::vector
、std::array
、std::deque
等容器的元素进行排序。它采用了高效的排序算法(通常是快速排序,但在某些实现中可能会使用其他算法,如堆排序(HeapSort)或插入排序(Insertion Sort))。以下是对 std::sort
的全面讲解,包括其用法、典型场景、以及代码示例。
1. 函数原型
std::sort
的基本原型如下:
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
**Compare**
是一个比较函数或仿函数(functor),定义了元素之间的比较逻辑。**RandomAccessIterator**
: 这是指向容器中元素的随机访问迭代器类型。**first**
: 这是指向待排序序列的第一个元素的迭代器。**last**
: 这是指向待排序序列的最后一个元素之后的位置的迭代器。
2. 排序的时间复杂度
std::sort
的时间复杂度通常为 O(n log n),其中 n 是待排序元素的数量。这个复杂度使其在大多数情况下都表现出色。尽管最坏情况下的复杂度可能达到 O(n^2),但实际应用中,快速排序通常提供了相当稳定的性能。
3. 使用场景
std::sort
适用于各种需要排序的场景,包括但不限于:
- 对数组、向量或其他容器中的元素进行排序。
- 对某个结构体的数组进行排序,可以通过自定义比较函数来实现复杂排序需求。
- 在需要对算法中的数据进行排序以提高效率时。
4. 常见用法
4.1. 对数组进行排序
以下是对数组进行排序的示例:
#include <iostream>
#include <algorithm> // 引入 sort 函数
using namespace std;int main() {int arr[] = {5, 2, 9, 1, 5, 6}; // 定义一个整数数组int n = sizeof(arr)/sizeof(arr[0]); // 计算数组大小// 对数组进行排序sort(arr, arr + n);// 输出排序后的数组for (int i = 0; i < n; i++) {cout << arr[i] << " "; // 打印每个元素}cout << endl;return 0;
}
4.2. 对 std::vector
进行排序
以下是对 std::vector
进行排序的示例:
#include <iostream>
#include <vector>
#include <algorithm> // 引入 sort 函数
using namespace std;int main() {vector<int> vec = {10, 5, 8, 1, 2}; // 定义一个整数向量// 对向量进行排序sort(vec.begin(), vec.end());// 输出排序后的向量for (int num : vec) {cout << num << " "; // 打印每个元素}cout << endl;return 0;
}
4.3. 自定义排序规则
可以通过传递一个自定义比较函数或函数对象来改变排序的规则。例如,按降序排序:
#include <iostream>
#include <vector>
#include <algorithm> // 引入 sort 函数
using namespace std;// 自定义比较函数,用于降序排序
bool compare(int a, int b) {return a > b;
}int main() {vector<int> vec = {10, 5, 8, 1, 2}; // 定义一个整数向量// 对向量进行降序排序sort(vec.begin(), vec.end(), compare);// 输出排序后的向量for (int num : vec) {cout << num << " "; // 打印每个元素}cout << endl;return 0;
}
4.4. 对结构体进行排序
假设我们有一个结构体 Person
,按年龄排序:
#include <iostream>
#include <vector>
#include <algorithm> // 引入 sort 函数
using namespace std;struct Person {string name;int age;
};// 自定义比较函数,用于按年龄排序
bool compareByAge(const Person& a, const Person& b) {return a.age < b.age;
}int main() {vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}}; // 定义一个 Person 向量// 对向量中的 Person 进行排序,按年龄sort(people.begin(), people.end(), compareByAge);// 输出排序后的向量for (const Person& p : people) {cout << p.name << " (" << p.age << ") "; // 打印每个 Person 的信息}cout << endl;return 0;
}
4.5. 部分排序
可以对容器的部分区域进行排序:
#include <iostream>
#include <vector>
#include <algorithm> // 引入 sort 函数
using namespace std;int main() {vector<int> vec = {10, 5, 8, 1, 2}; // 定义一个整数向量// 对向量的部分区域进行排序sort(vec.begin() + 1, vec.end() - 1);// 输出排序后的向量for (int num : vec) {cout << num << " "; // 打印每个元素}cout << endl;return 0;
}
好的,接着上面的讲解,我们来看一下如何使用比较函数对象来自定义排序逻辑。
4.6 使用比较函数对象
在C++中,sort
函数除了能够进行默认的升序排序外,还允许我们通过提供比较函数对象来自定义排序规则。比较函数对象是可以作为函数使用的类或结构体的实例,它能够根据我们定义的逻辑对元素进行比较。
4.6.1 greater<int>
函数对象
greater<int>
是标准库中的一个函数对象,用于实现降序排序。greater
模板类是定义在<functional>
头文件中的,它的作用是对两个对象进行“大于”比较。
示例代码:
#include <iostream>
#include <vector>
#include <algorithm> // 包含sort函数的头文件
#include <functional> // 包含greater的头文件using namespace std;int main() {// 创建一个包含整数的向量vector<int> v = {3, 1, 4, 1, 5};// 使用sort函数对向量进行排序,并使用greater<int>()作为比较函数对象,实现降序排序sort(v.begin(), v.end(), greater<int>());// 输出排序后的向量for (int i : v) {cout << i << " "; // 依次输出每个元素}return 0;
}
输出:
5 4 3 1 1
4.6.2 其他常见的函数对象
除了greater
外,C++标准库还提供了其他常见的函数对象,例如:
less<T>
:用于实现升序排序(默认行为)。greater_equal<T>
:用于实现“大于等于”比较。less_equal<T>
:用于实现“小于等于”比较。
这些函数对象可以直接用于sort
函数中,帮助我们根据不同的需求定制排序规则。
4.6.3 自定义函数对象
除了使用标准库提供的函数对象外,C++还允许我们自定义比较函数对象。例如,我们可以创建一个函数对象来实现按字符串长度排序。
示例代码:
#include <iostream>
#include <vector>
#include <algorithm> // 包含sort函数的头文件using namespace std;// 自定义函数对象,用于按字符串长度排序
struct LengthCompare {bool operator()(const string &a, const string &b) const {return a.length() < b.length(); // 返回a是否小于b}
};int main() {// 创建一个包含字符串的向量vector<string> v = {"apple", "banana", "pear", "grape"};// 使用sort函数,并传入自定义的比较函数对象LengthComparesort(v.begin(), v.end(), LengthCompare());// 输出排序后的向量for (const string &s : v) {cout << s << " "; // 依次输出每个字符串}return 0;
}
输出:
pear grape apple banana
在这个例子中,我们定义了一个名为LengthCompare
的函数对象,用于按字符串的长度进行排序。sort
函数会使用我们提供的逻辑来决定排序顺序。
5. 注意事项
std::sort
要求排序的范围必须是随机访问迭代器,因此它适用于std::vector
、数组等支持随机访问的容器。对于其他类型的容器(如链表),请使用其他排序算法,如std::list
的sort
成员函数。- 确保提供的比较函数是严格弱序的,即对于任意元素
a
,b
,c
,如果a < b
和b < c
,则必须有a < c
。 - 自定义比较函数必须满足这一特性,否则排序结果可能不正确。
6. 总结
std::sort
是 C++ 中一个功能强大且常用的排序算法。它适用于多种场景,包括对基本类型、用户自定义类型进行排序,以及对部分数据进行排序。通过自定义比较函数,可以灵活地控制排序的行为,以适应不同的需求。希望这个详细的讲解能帮助你更好地理解和应用 std::sort
。
- 📜 [ 声明 ] 由于作者水平有限,本文有错误和不准确之处在所难免,
- 本人也很想知道这些错误,恳望读者批评指正!
- 我是:勇敢滴勇~感谢大家的支持!