【蓝桥杯】每日练习 Day11 逆序对问题和多路归并
目录
前言
超快速排序
分析
代码
小朋友排队
分析
代码
鱼塘钓鱼
分析
代码
前言
本来计划今天写五道题的，结果计划赶不上变化，谁能告诉我我的时间都去哪了。。。
今天给大家带来三道题目，两道逆序对问题，分别用归并排序和树状数组求解，一道多路归并。
超快速排序
分析
看完题目首先想到的是冒泡排序，但是显然冒泡排序不属于“超快速排序”。
但是既然题目的最终目的是排序，那就肯定离不开排序算法。
学过线性代数的同学都知道，有一个东西叫做逆序数，指的就是一组排列中逆序对的个数。
逆序对能不能和本题的“交换次数”联系起来呢？主播很明确的告诉你们，最优的方案的交换次数就是逆序数。
如何证明呢？这个简单。
我们知道，在一个排列中交换两个相邻的元素，造成的影响是逆序数加一或者减一。
而逆序数的含义可以视为，存在一种方案使得每次相邻的两个元素交换，都能使得逆序数减一。
接下来的问题就是证明这种方案存不存在，请观察我下面的式子：
2， 3， 1
可以观察到前两个数字是已排序的，若要让这个排列的逆序数归零只需要交换3和1, 2和1，最终排列就变成了这样
1, 2, 3
逆序数归零了，并且我们每次交换操作造成的影响都是逆序数减一。
所以这种方案存在，具有充分性。
观察原排列，可以发现原排列可以分为两部分，即：2, 3 | 1，而每一部分内部都是排序过的。
观察上方的排列，有没有想起一个排序算法，没错，那么算法就是归并排序。
我们都知道归并排序是可以求逆序对数的，接下来主播就以自己的理解来解释归并排序为什么能够求逆序对数。
首先，我们将一个排列的逆序对视为一个集合S
随后，我们将排列分为两个区间，对集合进行划分，划分为区间内的逆序对和区间间的逆序对。
至于为什么可以划分很好证明，只需要证明三个子集没有包含关系即可，通过反证法很好证明。
那么整体的逆序对数就等于区间内的逆序对数 + 区间间的逆序对数。（容斥原理）
而归并排序就是利用这种思想，先消除区间内的逆序对，再消除区间间的逆序对，来达到计算逆序对数的效果。
而我们知道归并排序处理的每个区间都是排序后的两部分，所以根据上面的充分性，消除这样的区间的逆序对数的交换次数就是逆序对数。
所以问题就转化成了归并排序求逆序对数。
代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 500010;
int n;
int a[N],tmp[N];
LL merge_sort (int l,int r) {
if (l == r) return 0;
int mid = l + r >> 1;
LL ans = merge_sort (l,mid) + merge_sort (mid + 1,r);
int i = l,j = mid + 1,k = 0;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) tmp[k++] = a[i++];
else {
tmp[k++] = a[j++];
ans += mid - i + 1;
}
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (int i = l,j = 0;i <= r;i++,j++) a[i] = tmp[j];
return ans;
}
int main () {
while (cin >> n,n) {
for (int i = 1;i <= n;i++) cin >> a[i];
cout << merge_sort (1,n) << endl;
}
return 0;
}小朋友排队
分析
前面我们证明了逆序对数就是至少交换次数，但是这道题有写不一样，我们需要统计交换双方需要交换的次数那显然就不只是逆序对数了。
主播刚开始以为答案就是逆序对数乘以二，可是后来发现这个想法是错误的，因为每个元素的逆序对数只能代表他“主动”与别人交换的次数，并不能代表这个元素交换的次数，观察下方案例。
3， 2， 1
通过观察可以发现要想排序可以发现1要交换两次，3要交换两次，2也需要交换两次。
要讲明白一个知识点，主播需要先引入一个概念：
顺序对（主播自己起的名字，也不知道对不对），与逆序对相反，不过区别是顺序对指的是在这个元素之后小于这个元素的个数。
反过来看，对于后面的元素来说，可以将顺序对拆分成n部分，而其中的每一部分就是对于该元素的一个逆序对。
而后面的元素要想消除自己的逆序对就一定要与当前元素进行交换，我们将这种行为视为消除该元素的顺序对。
这样就同时统计了每个元素主动交换和被动交换的所有情况，因为最开始行为是区间划分，所以也无需判重。
主播这次是用树状数组实现，树状数组的写法很暴力，就是对每个数字统计在他前面且比他大的数字。
代码
// 树状数组求逆序对和顺序对
#include<iostream>
#include<cstring>
/*#define y second
#define x first*/
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 100010, P = 1000010;
int n;
int h[N];
int tree[P];
int st[N];
int lowbit(int x)
{
return x & -x;
}
void insert(int i, int x)
{
if(i >= P) return;
tree[i] += x;
insert(i + lowbit(i), x);
}
int find(int x)
{
if(x == 0) return tree[0];
return tree[x] + find(x - lowbit(x));
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n;h[i]++, i++) scanf("%d", h + i);
for(int i = 1; i <= n; i++)
{
st[i] += i - 1 - find(h[i]); //找大于当前数字的
insert(h[i], 1);
}
memset(tree, 0, sizeof(tree));
for(int i = n; i >= 1; i--)
{
st[i] += find(h[i] - 1); // 小于当前数字的
insert(h[i], 1);
}
LL l = 0;
for(int i = 1; i <= n; i++)
l += ((st[i] + 1) * (LL)st[i]) / 2;
printf("%lld", l);
return 0;
}鱼塘钓鱼
分析
首先想到可以搜索，但是数据量很大，而且状态也不好表示，所以先排除搜索。
首先先观察整体，可以发现每次换鱼塘只会消耗时间而不会带来重复收益，所以贪心思路是至多到达一次此鱼塘，即：一条路走下去，不要反复横跳。（这种找最优解的题一般是先分析整体看有没有明显重复的部分，随后就可以根据这些重复的部分确定贪心思路）。
随后发现了在哪个位置钓鱼的收益与时间无关，只和次数有关，接下来我们来思考一下能否将交换位置的时间剥离出来。
显然是可以的，随后我们可以枚举终点位置，即：每次只在1 ~ x的鱼塘内钓鱼。
接下来就变成了多个链表求最优和的问题。
可以发现每一个位置都是一个等差数列，并且考虑到有多个位置，每个位置地位相当，我们考虑使用多路归并算法。
有的人可能没有听说过这个算法，但其实这个算法很简单，合并两个有序数组用的就是多路归并算法。
随后根据等差数列的性质，最大的数字一定会出现在最表层，所以我们用堆来查找出外层的最大值依次增加即可。
代码
// 贪心 + 多路归并，枚举1 ~ n,每次多路归并查找
// 时间复杂度: n * t * logN, 时间肯定够。
#include<iostream>
#include<cstring>
#include<queue>
#define s second
#define f first
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, T, mx;
int a[N], b[N], t[N], st[N];
priority_queue<PII> pq;
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", a + i);
for(int i = 0; i < n; i++) scanf("%d", b + i);
for(int i = 1; i < n; i++) scanf("%d", t + i);
scanf("%d", &T);
for(int i = 0; i < n; i++) //枚举从0到i
{
int s = 0, l = 0;
pq = priority_queue<PII>(); //重构。
memset(st, 0, sizeof(st));
for(int j = 0; j <= i; j++)
{
pq.push({a[j], j});
s += t[j]; //第一部分贪心的时间
}
while(s < T)
{
PII x = pq.top(); pq.pop();
l += max(0, x.f);
st[x.s]++;
pq.push({a[x.s] - st[x.s] * b[x.s], x.s});
s++;
}
mx = max(mx, l);
}
printf("%d", mx);
return 0;
}