目录
排序
快速排序
归并排序
二分
高精度
高精度加法
高精度减法
高精度乘法
高精度除法
排序
快速排序
给定你一个长度为n的整数数列
请你使用快速排序对这个数列按照从小到大进行排序
并将排好序的数列按顺序输出
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n个整数(所有整数均在1~10^9范围内)，表示整个数列。
输出格式
输出共一行，包含n个整数，表示排好序的数列。
数据范围
1<n<100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
思路：快速排序，以中间的 元素 为坑位，从左边找比坑位大的，从右边找比坑位小的，然后交换左右两个位置的，直到两边相遇，对整个数组分成两半，对左边进行排序，右边排序。
解题代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100100;
ll a[N], q[N];
void quick_sort(ll q[], int l, int r)
{
if(l >= r)return;
ll x = q[(l + r) >> 1], i = l - 1, j = r + 1;
while(i < j)
{
do i++; while(q[i] < x);//左边找到比中间值大的
do j--; while(q[j] > x);//右边找到比中间值小的
if(i < j)swap(q[i], q[j]);//找到两个交换位置
}
quick_sort(q, l, j);//左边排序
quick_sort(q, j + 1, r);//右边排序
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)cin >> a[i];
// sort(a, a + n);//直接使用c++的函数
quick_sort(a, 0, n-1);
for(int i = 0; i < n; i++)cout << a[i] << ' ';
cout << "\n";
return 0;
}
练习题：786. 第k个数 - AcWing题库
归并排序
给定你一个长度为n的整数数列
请你使用归并排序对这个数列按照从小到大进行排序
并将排好序的数列按顺序输出
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数(所有整数均在1~109范内)，表示整个数列。
输出格式
输出共一行，包含n个整数，表示排好序的数列。
数据范围
1<n<100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
思路：归并排序，把数组分成两半，左边归并排序，右边归并排序，排完之后用两个指针，从左到右开始逐一对比，进行合并。
解题代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100100;
ll a[N], q[N];
void merge_sort(ll a[N], int l , int r)
{
if(l >= r)return;
int mid = l + r >> 1;
merge_sort(a, l, mid);//左边归并排序
merge_sort(a, mid + 1, r);//右边归并排序
int i = l, j = mid + 1, k = l;
while(i <= mid && j <= r){//合并
if(a[i] < a[j]){
q[k++] = a[i++];
}else{
q[k++] = a[j++];
}
}
while(i <= mid) q[k++] = a[i++];//扫尾
while(j <= r) q[k++] = a[j++];
for(int i = l; i <= r; i++) a[i] = q[i];
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)cin >> a[i];
merge_sort(a, 0, n-1);
for(int i = 0; i < n; i++)cout << a[i] << ' ';
cout << "\n";
return 0;
}
练习题：788. 逆序对的数量 - AcWing题库
tip：求逆序对 ，根据归并分治的原理，在判断a[i], aj[j]的时候统计。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100100;
ll a[N], q[N];
ll merge_sort(ll a[N], int l , int r)
{
if(l >= r)return 0;
int mid = l + r >> 1;
//左边逆序对数量 + 右边逆序对数量
ll res = merge_sort(a, l, mid)+merge_sort(a, mid + 1, r);
int i = l, j = mid + 1, k = l;
while(i <= mid && j <= r){//合并
if(a[i] <= a[j]){
q[k++] = a[i++];
}else{// a[i] > a[j] 构成逆序对
q[k++] = a[j++];
res += mid - i + 1;
//a[j] < a[i] <= a[i+1] <= a[i+2] ... <= a[mid]
//故比a[j]大的有 a[i]到a[mid]
}
}
while(i <= mid) q[k++] = a[i++];//扫尾
while(j <= r) q[k++] = a[j++];
for(int i = l; i <= r; i++) a[i] = q[i];
return res;
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)cin >> a[i];
cout << merge_sort(a, 0, n-1);
cout << "\n";
return 0;
}
二分
给定一个按照升序排列的长度为 n的整数数组，以及个查询
对于每个查询，返回一个元素的起始位置和终止位置(位置从0开始计数)。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数n和，表示数组长度和询问个数第二行包含n个整数(均在1~10000范围内)，表示完整数组接下来 q 行，每行包含一个整数 k，表示一个询问元素
输出格式
共q行，每行包含两个整数，表示所求元素的起始位置和终止位置如果数组中不存在该元素，则返回 -1 -1
数据范围
1<n<100000
1<q<10000
1<k<10000
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1
思路：二分的前提是数组必须是有序的，在找数的时候，如果当前数的比要找的数大，说明要找的数在当前数之后，如果当前的数比要找的数小，说明要找的数在当前数之前。
解题代码
#include <bits/stdc++.h>
using namespace std;
int a[100100];
//找到不小于该元素的最小位置
int leftfind(int a[], int l, int r, int k)
{
while(l < r){
int mid = (l + r) >> 1;
if(a[mid] >= k){
r = mid;
}else {
l = mid + 1;
}
}
return a[l]==k ? l : -1;
}
//找到不大于该元素的最大位置
int rightfind(int a[], int l, int r, int k)
{
while(l < r){
int mid = (l + r + 1) >> 1;
if(a[mid] <= k){
l = mid;
}else {
r = mid - 1;
}
}
return a[l] == k ? l : -1;
}
int main()
{
int n, q;
cin >> n >> q;
for(int i = 0; i < n; i++)cin >> a[i];
while(q--)
{
int k; cin >> k;
/* C++内置函数
int idx = lower_bound(a, a+n, k)-a ;
if(a[idx] != k)idx = -1;
cout << idx << " ";
idx = upper_bound(a, a+n, k)-a;
if(a[idx-1] != k)idx = -1;
else idx --;
cout << idx << "\n";*/
cout << leftfind(a, 0, n-1, k) << " ";
cout << rightfind(a, 0, n-1, k) << "\n";
}
return 0;
}
练习题： 790. 数的三次方根 - AcWing题库
给定一个浮点数n，求它的三次方根
输入格式共一行，包含一个浮点数n。输出格式共一行，包含一个浮点数，表示问题的解。注意，结果保留6位小数数据范围
-10000 <n<10000
输入样例：1000.00
输出样例：10.000000
#include <bits/stdc++.h>
using namespace std;
int main()
{
double n;
cin >> n;
double l = -10000, r = 10000, mid = 0;
while(r-l >= 1e-7)//精度小于1e-7
{
mid = (l + r ) / 2;
if(mid*mid*mid >= n){//三次方根大于 n，数给大了
r = mid;
}else{
l = mid;
}
}
printf("%.6f\n", l);
return 0;
}
高精度
高精度加法
给定两个正整数(不含前导0)，计算它们的和
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的和。
数据范围
1<整数长度<100000
输入样例:
12
23
输出样例:
35
思路：加法运算都是从后面的位数开始相加，然后考虑是否需要进位。把两个字符串从后面开始相加，以s判断是否需要进位，加完之后，如果A或者B还没加完，就处理一下，最后把结果倒着输出。
解题代码
#include <bits/stdc++.h>
using namespace std;
// string形式
string add(const string& A, const string& B)
{
string C ="";
int s = 0;
for (int i = A.size()-1, j = B.size()-1; i >= 0 || j >= 0 || s > 0; i--, j--)
{
if (i >= 0) s += (A[i] - '0');
if (j >= 0) s += (B[j] - '0');
C += ((s % 10) + '0');
s /= 10;
}
reverse(C.begin(), C.end());
return C;
}
int main()
{
string a, b;
cin >> a >> b;
vector<int> res;
int i = a.size()-1, j = b.size()-1;
while(i >= 0 && j >= 0){//从末尾开始对应数位相加
res.push_back((a[i--]-'0')+(b[j--]-'0'));
}
while(i >= 0)res.push_back(a[i--]-'0');//a还有位就再添上去
while(j >= 0)res.push_back(b[j--]-'0');//b还有位就添上去
for(int i = 0; i < res.size(); i++){//查看每个位是否超过10，超过就要进1给下一位
if(res[i] > 9){
if(i==res.size()-1)res.push_back(1);
else
res[i+1] += 1;
res[i] %= 10;
}
}
for(int i = res.size()-1; i>=0; i--)cout << res[i];//倒序输出
return 0;
}
高精度减法
给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的差。
数据范围
1≤整数长度≤10^5
输入样例：
32
11
输出样例：
21
思路：如果A >= B，减完之后都是正数；相反即为负数，变成 -(B-A）。减法同样是从后面开始逐位相减，逆置两个字符串，同样用t来标记是否需要借位，考虑是否有无效0，最后逆序输出。
解题代码：
#include <bits/stdc++.h>
using namespace std;
//判断A 是否 大于等于 B
bool check(const string& A, const string& B)
{
if(A.size() != B.size())return A.size() > B.size();
return A >= B;
}
string sub(string& A, string& B)
{
string C = "";
int t = 0;
//反转从后面开始相减
reverse(A.begin(), A.end());
reverse(B.begin(), B.end());
for(int i = 0; i < A.size(); i++){
t = A[i]-'0' - t;//t是否已借1给后面
if(i < B.size()) t -= B[i]-'0';//B是否有位需要减
C += (char)((t + 10)%10+'0');
if(t < 0)t = 1;
else t = 0;
}
while(C.size() > 1 && C.back() == '0')C.pop_back();//去除末尾有无效0
reverse(C.begin(), C.end());//反转为结果
return C;
}
int main()
{
string a, b;
cin >> a >> b;
if(check(a, b))
cout << sub(a, b);
else
{
cout << "-"<< sub(b, a);
}
return 0;
}
高精度乘法
高精度A x 低精度B
给定两个非负整数（不含前导 00） A和 B，请你计算 A×B 的值。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共一行，包含 A×B 的值。
数据范围
1≤A的长度≤100000
0≤B≤10000
输入样例：
2
3
输出样例：
6
思路： 高精度A从最后一位开始逐位乘以B，个位为当前位的结果，其余的需要加上下一位的。
解题代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
string a;
int b;
cin >> a >> b;
vector<int> res;
int t = 0;
for(int i = a.size() -1; i >= 0; i--){//从后面开始每一位都乘以b
t += (a[i]-'0')*b;
res.push_back(t%10);
t/=10;
}
//每一位乘完最后剩余的加回去
while(t){
res.push_back(t%10);
t/=10;
}
if(b==0)cout << 0;//如果b是0，直接等于0
else
for(int i = res.size()-1; i >= 0; i--)cout << res[i];
return 0;
}
高精度除法
给定两个非负整数(不含前导0) A，B，请你计算A/B的商和余数。
输入格式
共两行，第一行包含整数A，第二行包含整数 B
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1A的长度<100000
1 < B< 10000,
B一定不为0
输入样例：
7
2
输出样例：
3
1
思路：高精度除法与前面不同，它的计算方式是从前面开始除，逐位除b，余数*10+下一位的数再继续除，直到所有的数除完，没得除了就剩余数。
解题代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
string a;
int b;
cin >> a >> b;
int t = 0;
string res = "";
for(int i = 0; i < a.size(); i++){
t = t*10 + (a[i]-'0');//前一位除完的余数*10+当前的位
res += (char)(t/b + '0');//除b后的结果
t = t % b;//余数
}
int f = 0;
for(int i = 0; i < res.size(); i++)
{
if(f==0&&res[i]=='0'&&i!=res.size()-1)continue;//最前面的0，但是不能是最后一个0
else{
cout << res[i];
f = 1;
}
}
cout << "\n";
cout << t % b;//余数
return 0;
}
本篇是介绍基础算法中关于排序，二分，高精度的算法代码。算法这一路坎坷没法讲，也讲不完，反正坚持下去就是胜利。所以，加油吧，友友们！！！
