2025年算法-求解逆序对问题

大家好，我是讯享网，很高兴认识大家。

算法记录：逆序对问题

逆序对-如果存在l<r，并且X(l)>X(r)，则称为一个逆序对。逆序对的个数等于在朴素稳定排序情况下，相邻数交换的次数。

1.暴力激活成功教程

利用多重循环遍历，从i+1~n找出比他小的数的个数。

eg： 3 5 2 1 0 4 9

逆序对有：（3，2）（3，1) （3，0) (5,2）（5，2）（5，1）（5，0）（5，4）（2，1）（2，0）（1，0）

虽然可以求解，但大多会超时，不建议使用。

2.归并排序（把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行）

向下递归划分

讯享网

向上返回归并

#include<cstdio> using namespace std; int A[10],n; int megersort(int l,int r){//归并排序 if(l>=r)return 0; int mid=(l+r)/2; int t=megersort(l,mid)+megersort(mid+1,r); int L=l,R=mid+1,ans=l; int *p=new int[n+1];//左部归并好的部分 for(int i=l;i<=mid;i++){ p[i]=A[i]; } int *q=new int[n+1];//右部归并好的部分 for(int i=mid+1;i<=r;i++){ q[i]=A[i]; } while(L<=mid&&R<=r){ if(p[L]<=q[R]){//左部同右部比较 A[ans++]=p[L++]; t+=R-mid-1; }else{ A[ans++]=q[R++]; } } while(L<=mid){//左部有剩余 A[ans++]=p[L++]; t+=r-mid; } while(R<=r){ A[ans++]=q[R++]; } return t; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&A[i]); } printf("逆序对:%d",megersort(1,n)); for(int i=1;i<=n;i++){ printf("%d ",A[i ]); } return 0; }

讯享网

附带算法题：

描述

假设一间浴室最多只能洗一个人，一个人当然也只需洗一次澡，并且不能洗到一半就出来噢，假设当前共有三间浴室。如果三个浴室都有人在洗澡，其它需要洗澡的人就需要在任意一个浴室前排队，等待前一个人洗完再进去洗。

假设在t=0的时刻开始有热水，大家陆陆续续的前去洗澡，n个人分别在a1,a2,...,an时刻到达浴室，为了简化问题，假设每个人洗澡均需b的时间，并且忽略在浴室内移动的时间。请问最早什么时刻，所有的n个人均完成洗澡。

输入

输入有多组样例，第一行是一个整数T，表示样例个数。接下来每组样例的第一行是一个整数n，表示将要洗澡的人数，第二行有n个整数ai，表示第i个人抵达浴室的时间，最后一行是一个整数b，表示一个人洗澡所需的时间。1≤T≤250，1≤n≤600，0≤ai≤10000，1≤b≤1500。

输出

对于每组数据，输出一个整数，表示最后一个人最早洗澡完成的时间。

思路：把三个浴室看成三条时间线，先将输入的每组数据从小到大排序，比较下一个人到达的时间与第一次三个人最小时间比较，如果下一个人到达时间比第一次的最小时间大，则把第一次最小时间替换为下一个人到达的时间，并将其加上洗澡所需时间否则直接在第一次最小时间加上洗澡所需时间，不断重复进行下一轮，最终所得结果即为最后一个人最早洗澡完成的时间。

讯享网#include <bits/stdc++.h> using namespace std; int main(){ int N ; scanf("%d",&N); while(N--){ int t1 = 0,t2 = 0 ,t3 = 0,n,mod;//mod为洗澡所需时间 int num[10000]={0},minTime; sort(num,num+n); scanf("%d",&n); for(int i = 0 ; i < n ; i++){ scanf("%d",&num[i]); } scanf("%d",&mod); sort(num,num+n);//将每个人到达时间从小到大排序 for(int i = 0 ; i < n ; i++){ minTime = min(t1,t2); minTime = min(minTime,t3);//获得第一次三个人洗澡最短时间 if(num[i] <= minTime){ if (minTime == t1) t1+=mod; else if (minTime == t2) t2+=mod; else t3+=mod; }else{ if (minTime == t1) t1=num[i]+mod; else if (minTime == t2) t2=num[i]+mod; else t3=num[i]+mod; } } minTime = max(t1,t2); minTime = max(minTime,t3);//比较取得最小时间 printf("%d\n",minTime); } }

2025年算法-求解逆序对问题

相关推荐