本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】学而思编程逆序对【题目描述】对于一个包含N NN个非负整数的数组A [ 1.. n ] A[1..n]A[1..n]如果有i j ijij且A [ i ] A [ j ] A[i]A[j]A[i]A[j]则称( A [ i ] , A [ j ] ) (A[i],A[j])(A[i],A[j])为数组A AA中的一个逆序对。例如数组( 3 1 4 5 2 ) (31452)(31452)的逆序对有( 3 , 1 ) , ( 3 , 2 ) , ( 4 , 2 ) , ( 5 , 2 ) (3,1),(3,2),(4,2),(5,2)(3,1),(3,2),(4,2),(5,2)共4 44个。给定一个数组求该数组中包含多少个逆序对。【输入】第一行一个数n nn表示数组中有n nn个数。第二行n nn个数表示给定的数组。数组中每个数字不超过10 9 10^9109。【输出】输出数组中逆序对的数目。【输入样例】6 5 4 2 6 3 1【输出样例】11【算法标签】#归并排序【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN500005;intn;// 数组长度inta[N],b[N];// a: 原始数组, b: 临时数组intans;// 逆序对数量// 归并排序函数计算逆序对数量voidmerge_sort(intl,intr){if(lr)return;// 如果子数组只有一个元素则不需要排序直接返回intmid(lr)/2;// 计算中点merge_sort(l,mid);// 递归地对左半部分进行归并排序merge_sort(mid1,r);// 递归地对右半部分进行归并排序intxl,ymid1;// x: 左半部分的指针, y: 右半部分的指针intcntl-1;// b数组的指针// 合并两个有序子数组while(xmidyr)// 只要左右两端子数组都不为空{if(a[x]a[y])// 将两段子数组左端点较小者插入b数组{b[cnt]a[x];// 左半部分元素较小x;}else// 右半部分元素较小{b[cnt]a[y];// 右半部分元素较小y;ansmid-x1;// 统计逆序对数量}}// 合并过程中其中一个子数组的元素已全部合并完成而另一个子数组仍有剩余元素的情况for(intix;imid;i)// 如果左半部分还有剩余的元素将它们复制到b中{b[cnt]a[i];}for(intiy;ir;i)// 如果右半部分还有剩余的元素将它们复制到b中{b[cnt]a[i];}for(intil;ir;i)// 将b中已经排序好的部分复制回a中完成合并{a[i]b[i];}}signedmain(){cinn;// 读取数组长度for(inti1;in;i)// 读取数组元素{cina[i];}merge_sort(1,n);// 调用归并排序函数coutansendl;// 输出逆序对数量return0;}【运行结果】6 5 4 2 6 3 1 11