前言

向量和栈、队列一样，都是STL容器中的一种。

STL容器是一个庞大的“家庭”，之后会学习到更多的容器。

介绍

vector 是 C++ 标准模板库（STL）中的一种动态数组容器，它能够在运行时自动调整大小，是实际开发中最常用的容器之一。

其核心特点是动态扩容：无需预先指定容量，可以随时添加或删除元素，当空间不足时，vector 会自动重新分配更大的内存空间并将原有元素移动到新内存中。这一特性使得程序员无需关心底层内存管理，大大降低了使用门槛。

vector 的元素在内存中连续存储，支持通过下标进行 O(1) 时间的随机访问，这一点与普通数组完全相同。这种连续存储的特性还带来了良好的缓存局部性，使得遍历操作非常高效。同时，vector 会自动记录当前元素个数和已分配的容量，通过预留空间策略减少频繁扩容带来的性能损耗。

与静态数组相比，vector 提供了更高的灵活性和安全性；与链表等容器相比，它拥有更好的随机访问性能和缓存友好性。正是这种兼顾了数组的高效访问和动态扩展的灵活性的特点，使得 vector 成为 C++ 中最基础、最通用的序列容器，广泛应用于算法实现、数据存储、缓冲区管理等各类场景。

代码框架

使用 vector 需要用到 <vector> 头文件

#include <vector>

手写就不展示了，有点太麻烦了

其实是我懒

例题

洛谷 P13457 [GCJ 2008 #1A] Minimum Scalar Product

题目大意

给你  个数  和 ，定义标量积  你要通过改变他们的顺序使得标量积最小，求这个最小标量积。

注意多组数据。

思路

策略是将 ​ 升序排序， 降序排列，以下给出证明

考虑 

需证明 ，即

设 ，则 

，证毕。

当 ，每两个数都可以像如上排序，从而取到最小值。

Code

1.带注释详解版

#include <iostream>
#include <algorithm>
#include <vector>
#define Please return
#define AC 0
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
using namespace std;
using ll = long long; // 最大 1e5 * 1e5 * 800 = 8e12，要用长整
ll t, n, v, I; // t n v 如题面所见，I 是测试组数

int main() {
	cin >> t;
	while (t--) { // 多组数据
		I++;
		cin >> n; // 输入
		vector<ll> v1, v2;
		for (int i = 1; i <= n; i++) {
			cin >> v;
			v1.push_back(v);
		}
		for (int i = 1; i <= n; i++) {
			cin >> v;
			v2.push_back(v);
		}
		sort(v1.begin(), v1.end(), less<ll>()); // 按策略排序并计算
		sort(v2.begin(), v2.end(), greater<ll>());
		ll ans = 0;
		for (int i = 0; i < n; i++) {
			ans += v1[i] * v2[i];
		}
		cout << "Case #" << I << ": " << ans << endl; // 输出
	}
	Please AC;
}

2.无注释纯享版

#include <iostream>
#include <algorithm>
#include <vector>
#define Please return
#define AC 0
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
using namespace std;
using ll = long long;
ll t, n, v, I;

int main() {
	cin >> t;
	while (t--) {
		I++;
		cin >> n;
		vector<ll> v1, v2;
		for (int i = 1; i <= n; i++) {
			cin >> v;
			v1.push_back(v);
		}
		for (int i = 1; i <= n; i++) {
			cin >> v;
			v2.push_back(v);
		}
		sort(v1.begin(), v1.end(), less<ll>());
		sort(v2.begin(), v2.end(), greater<ll>());
		ll ans = 0;
		for (int i = 0; i < n; i++) {
			ans += v1[i] * v2[i];
		}
		cout << "Case #" << I << ": " << ans << endl;
	}
	Please AC;
}

附录：vector 常用函数

vector常用函数

函数名	功能
v.push_back(x)	在 v 尾部加入一个元素 x
v.pop_back()	删除 v 尾部的元素
v.erase(it)	删除 v 中迭代器为 it 的元素
v.clear()	清空 v
v.front()	返回 v 的头部元素
v.back()	返回 v 的尾部元素
v.size()	返回 v 的元素数量
v.empty()	返回 v 是否为空
v.resize(x)	将 v 的大小修改为 x
v.begin()	返回 v 的第一个位置的迭代器
v.end()	返回 v 的最后一个位置的后一个位置的迭代器

感谢观看！

有问题欢迎指出