网站版面如何布局,网站建设公司天强科技,大连森秀网络推广,做暧昧在线网站目录 引言概念一、火柴排队二、归并排序三、逆序对的数量四、小朋友排队五、超级快速排序 引言
关于这个归并排序#xff0c;考察的还是挺多的#xff0c;在笔试面试中会问你#xff0c;或者直接让你写一个归并排序#xff0c;还有竞赛中有时也会考察#xff0c;不过一般… 目录 引言概念一、火柴排队二、归并排序三、逆序对的数量四、小朋友排队五、超级快速排序 引言
关于这个归并排序考察的还是挺多的在笔试面试中会问你或者直接让你写一个归并排序还有竞赛中有时也会考察不过一般都是小题主要是考察递归和递推看你对这个过程的理解所以还是很重要的加油 概念
归并排序参考博客归并排序 冒泡排序交换的次数就是逆序对的数量如果要求数量可用归并排序来求解超快速排序就是归并排序 一、火柴排队
标签归并排序
思路只要把 a a a 和 b b b 中的数由小到大一一对应这样的结果是最小的。但是不必要两个数组都排序我们可以把 a a a 抽象成有序的就是把 a a a 当作有序然后让 b b b 去排成这种有序的。然后最优解就是求逆序对的数量。
题目描述
涵涵有两盒火柴每盒装有 n 根火柴每根火柴都有一个高度。现在将每盒中的火柴各自排成一列同一列火柴的高度互不相同两列火柴之间的距离定义为∑i1n(ai−bi)2其中 ai 表示第一列火柴中第 i 个火柴的高度bi 表示第二列火柴中第 i 个火柴的高度。 每列火柴中相邻两根火柴的位置都可以交换请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离最少需要交换多少次如果这个数字太大请输出这个最小交换次数对 99,999,997 取模的结果。输入格式
共三行第一行包含一个整数 n表示每盒中火柴的数目。 第二行有 n 个整数每两个整数之间用一个空格隔开表示第一列火柴的高度。第三行有 n 个整数每两个整数之间用一个空格隔开表示第二列火柴的高度。输出格式
输出共一行包含一个整数表示最少交换次数对 99,999,997 取模的结果。数据范围
1≤n≤105,0≤火柴高度≤231−1
输入样例
4
2 3 1 4
3 2 1 4
输出样例
1示例代码
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 100010, MOD 99999997;int n;
int a[N], b[N], c[N], p[N];void work(int a[])
{for (int i 1; i n; i ) p[i] i;sort(p 1, p n 1, [](int x, int y) {return a[x] a[y];});for (int i 1; i n; i ) a[p[i]] i;
}int merge_sort(int l, int r)
{if (l r) return 0;int mid l r 1;int res (merge_sort(l, mid) merge_sort(mid 1, r)) % MOD;int i l, j mid 1, k 0;while (i mid j r)if (b[i] b[j]) p[k ] b[i ];else p[k ] b[j ], res (res mid - i 1) % MOD;while (i mid) p[k ] b[i ];while (j r) p[k ] b[j ];for (i l, j 0; j k; i , j ) b[i] p[j];return res;
}int main()
{scanf(%d, n);for (int i 1; i n; i ) scanf(%d, a[i]);for (int i 1; i n; i ) scanf(%d, b[i]);work(a), work(b);for (int i 1; i n; i ) c[a[i]] i;for (int i 1; i n; i ) b[i] c[b[i]];printf(%d\n, merge_sort(1, n));return 0;
}二、归并排序
标签归并排序、模板题
思路模板题没啥说的
题目描述
给定你一个长度为 n 的整数数列。请你使用归并排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。输入格式
输入共两行第一行包含整数 n。第二行包含 n 个整数所有整数均在 1∼109 范围内表示整个数列。输出格式
输出共一行包含 n 个整数表示排好序的数列。数据范围
1≤n≤100000
输入样例
5
3 1 2 4 5
输出样例
1 2 3 4 5示例代码
#include bits/stdc.husing namespace std;typedef long long LL;const int N 1e510;int n;
int a[N], backup[N];void merge_sort(int l, int r)
{if(l r) return;int mid l r 1;merge_sort(l, mid), merge_sort(mid1, r);int i l, j mid 1, k 0;while(i mid j r){if(a[i] a[j]) backup[k] a[i];else backup[k] a[j];}while(i mid) backup[k] a[i];while(j r) backup[k] a[j];for(int i l, j 0; i r; i, j) a[i] backup[j];
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n;for(int i 0; i n; i) cin a[i];merge_sort(0, n - 1);for(int i 0; i n; i) cout a[i] ;cout endl;return 0;
}三、逆序对的数量
标签归并排序、模板题
思路模板题没啥说的
题目描述
给定一个长度为 n 的整数数列请你计算数列中的逆序对的数量。逆序对的定义如下对于数列的第 i 个和第 j 个元素如果满足 ij 且 a[i]a[j]则其为一个逆序对否则不是。输入格式
第一行包含整数 n表示数列的长度。第二行包含 n 个整数表示整个数列。输出格式
输出一个整数表示逆序对的个数。数据范围
1≤n≤100000数列中的元素的取值范围 [1,109]。输入样例
6
2 3 4 5 6 1
输出样例
5示例代码
#include bits/stdc.husing namespace std;typedef long long LL;const int N 1e510;int n;
int a[N], backup[N];LL merge_sort(int l, int r)
{if(l r) return 0;int mid l r 1;LL res merge_sort(l, mid) merge_sort(mid1, r);int i l, j mid1, k 0;while(i mid j r){if(a[i] a[j]) backup[k] a[i];else{res mid - i 1;backup[k] a[j];}}while(i mid) backup[k] a[i];while(j r) backup[k] a[j];for(int i l, j 0; i r; i, j) a[i] backup[j];return res;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n;for(int i 0; i n; i) cin a[i];LL res merge_sort(0, n-1);cout res endl;return 0;
}四、小朋友排队
标签归并排序、树状数组
思路1 树状数组 首先最优解交换的次数就是冒泡排序的次数 k k k 也就是逆序对的个数 k k k 了我们只要知道每一个小朋友的交换次数就可以用公式计算出来不高兴程度并算出总和。每个小朋友的交换次数等于在这之前的大的个数加上后面小的个数因为这也就相当于两倍逆序对的个数这就说明这种做法就是最优的。我们可以用树状数组来模拟用下标来表示高度元素代表该高度的人数然后可以从前往后插入求第 i i i 个人的高度 h [ i ] h[i] h[i] 前面有多少人比他高用前缀和思想同理可以从后往前遍历就能知道第 i i i 号人的高度 h [ i ] h[i] h[i] 后面有多少人比他低就可以得知 s u m [ i ] sum[i] sum[i] 然后就是一个等差数列用公式就每个人之和即可。
题目描述
示例代码1 树状数组
#include bits/stdc.husing namespace std;typedef long long LL;const int N 1e610;int n;
int h[N], tr[N];
LL sum[N];int lowbit(int x)
{return x -x;
}void add(int a, int b)
{for(int i a; i N; i lowbit(i)) tr[i] b;
}LL query(int x)
{LL res 0;for(int i x; i; i - lowbit(i)) res tr[i];return res;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n;for(int i 0; i n; i) cin h[i], h[i];for(int i 0; i n; i){sum[i] query(N - 1) - query(h[i]);add(h[i], 1);}memset(tr, 0, sizeof tr);for(int i n - 1; i 0; --i){sum[i] query(h[i] - 1);add(h[i], 1);}LL res 0;for(int i 0; i n; i) res (1 sum[i]) * sum[i] / 2;cout res endl;return 0;
}五、超级快速排序
标签归并排序
思路其实就是求逆序对的数量拿归并排序一做即可。
题目描述
在这个问题中您必须分析特定的排序算法----超快速排序。该算法通过交换两个相邻的序列元素来处理 n 个不同整数的序列直到序列按升序排序。对于输入序列 9 1 0 5 4超快速排序生成输出 0 1 4 5 9。您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。输入格式
输入包括一些测试用例。每个测试用例的第一行输入整数 n代表该用例中输入序列的长度。接下来 n 行每行输入一个整数 ai,代表用例中输入序列的具体数据第 i 行的数据代表序列中第 i 个数。当输入用例中包含的输入序列长度为 0 时输入终止该序列无需处理。输出格式
对于每个需要处理的输入序列输出一个整数 op代表对给定输入序列进行排序所需的最小交换操作数每个整数占一行。数据范围
0≤n500000,一个测试点中所有 n 的和不超过 500000。0≤ai≤999999999
输入样例
5
9
1
0
5
4
3
1
2
3
0
输出样例
6
0示例代码
#include bits/stdc.husing namespace std;typedef long long LL;const int N 5e510;int n;
int a[N], backup[N];LL merge_sort(int l, int r)
{if(l r) return 0;LL res 0;int mid l r 1;res merge_sort(l, mid) merge_sort(mid1, r);int i l, j mid 1, k 0;while(i mid j r){if(a[i] a[j]) backup[k] a[i];else{res mid - i 1;backup[k] a[j];}}while(i mid) backup[k] a[i];while(j r) backup[k] a[j];for(int i l, j 0; i r; i, j) a[i] backup[j];return res;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);while(cin n, n){for(int i 0; i n; i) cin a[i];LL res merge_sort(0, n-1);cout res endl;}return 0;
}
