腾讯笔试题—

腾讯笔试题——逆序对

article/2025/11/5 14:02:24

这题花了我非常多时间，ac率从10％ --> 50％ --> 60％ --> 70％ --> 80％ --> 100％，被这题疯狂支配几个小时！
最关键没有详细的题解可以参考，大数据报错时也无法调试，只有反复一遍又一遍分析，下面把我踩到的坑记录下，或许可以帮到遇到同样问题的人。

题目描述

逆序对
在这里插入图片描述

简而言之，就是给你一组数，然后多次翻转，每次翻转后求解逆序对数量。

分析

要求解逆序对，首先可以想到用归并排序求解逆序对，因此首先需要掌握这一题。
归并排序求解逆序对
我的代码
另外掌握了利用归并排序求解逆序对后，可以想到暴力解，即每次翻转，然后利用归并排序求解逆序对，不过复杂度太高，只能通过50%的数据。显然每次都要归并排序成本太高，那么可不可只使用一次归并排序哪？

可以发现，逆序对翻转后，变成顺序对，如1 2，翻转变成2 1。因此我们需要记录不同长度的逆序对和顺序对的数量，当翻转时，仅需交换小于等于该翻转长度的逆序对和顺序对（因为大于翻转长度的逆序对不会收到影响），将所有的逆序对加起来即可得到结果。
举个例子，如 2 1 4 3，长度为2 ^ 1的逆序对数量为2（2 1一对，4 3一对），长度为2 ^ 2的逆序对数量为0（2 1 4 3中2 1 和4 3不构成逆序对，不要重复计算）。之后便可以只交换逆序对和顺序对数量，求逆序对的和即可。
顺序对怎么计算，可以考虑用总数-逆序对-相等的对（相等的对翻转了也不是逆序对，只过了百分之60的可以看看是否考虑到了两个数相等的情况），不过我这么做数据只过了70%，80%，最后也没发现错在哪，所以换了种思路，即将整个数组倒过来，求解逆序对，就是原数组的顺序对。

代码

#include <vector>
#include <iostream>
#include <math.h>
using namespace std;
void merge(vector<long long int>&nums, long long int lbegin, long long int lend,long long int rbegin,long long int rend,long long int index,vector<long long int>&cnt) {long long int p1 = lbegin, p2 = rbegin;vector<long long int> tmp(rend - lbegin + 1);long long int i = 0;long long int pairsCnt = 0;while (p1 <= lend && p2 <= rend) {if (nums[p1] <= nums[p2]) {tmp[i++] = nums[p1++];}else if(nums[p1]>nums[p2]){pairsCnt += (lend - p1 + 1);tmp[i++] = nums[p2++];}}while (p1 <= lend) {tmp[i++] = nums[p1++];}while (p2 <= rend) {tmp[i++] = nums[p2++];}for (int i = 0; i < tmp.size(); i++) {nums[lbegin++] = tmp[i];}cnt[index] += pairsCnt;
}
void mergeSort(vector<long long int>& nums, long long int begin, long long int end, long long int index,vector<long long int>& cnt) {if (begin == end)return;long long int mid = (end - begin) / 2 + begin;mergeSort(nums, begin, mid,index-1,cnt);mergeSort(nums, mid + 1, end,index-1,cnt);merge(nums, begin, mid, mid + 1, end,index,cnt);
}
int main() {ios::sync_with_stdio(false);long long int n;cin >> n;long long int cnt = pow(2, n);vector<long long int> nums;while (cnt--) {long long int tmp;cin >> tmp;nums.push_back(tmp);}vector<long long int> order(n+1,0);//保存不同长度的顺序对个数vector<long long int> reOrder(n+1,0);//保存不同长度的逆序对个数vector<long long int> reverse_nums(nums.rbegin(), nums.rend());mergeSort(nums, 0, nums.size() - 1,n,reOrder);mergeSort(reverse_nums, 0, reverse_nums.size() - 1, n,order);long long int m;cin >> m;while (m--) {long long int q;cin >> q;long long int cnt = 0;for (long long int i = 1; i <= q; i++) {swap(order[i], reOrder[i]);//每次反转后，需要交换q范围内顺序对和逆序对的数量}for (long long int i = 1; i <= n; i++) {cnt += reOrder[i];}cout << cnt << endl;}system("pause");return 0;
}