7-6 逆序对

作者 c++课程组

单位 湖州师范学院

求逆序对。

输入格式:

第一行是一个整数n，（n<=1000,000）表示输入序列的长度，接下来一行是n个整数(每个数的绝对值小于109)。

输出格式:

一个数，表示逆序对个数(逆序即任意一对数前面的数比后面的数大即为一对逆序对)。

输入样例:

10

1 3 5 7 9 8 4 2 6 10

输出样例:

逆序对对数可能很大，计数器要用long long：

14

说明：样例中如1和3不是逆序对，而3和2是1对逆序对，例子中共有14对逆序对。题目中可能有某些数字出现多次的情况。

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

参考代码C（gcc）

#include 
#define N 1000000
int n,a[N],b[N];
long long  cnt=0;
void f(int L,int R){if(L==R) return;int m=(L+R)/2;int k1=L,k2=m+1,k=L;f(L,m);f(m+1,R);while(k1<=m&&k2<=R){if(a[k1]<=a[k2]){b[k]=a[k1];k++,k1++;}else{b[k]=a[k2];k++,k2++;cnt=cnt+m-k1+1;}}while(k1<=m){b[k]=a[k1];k++,k1++;}while(k2<=R){b[k]=a[k2];k++,k2++;}for(int i=L;i<=R;i++)a[i]=b[i];
}
int main(){int i ;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);f(1,n);printf("%lld",cnt);return 0;
}

7-7 堆排序

作者 黄龙军

单位 绍兴文理学院

给定一个整数序列，请按非递减序输出采用堆排序的各趟排序后的结果。

输入格式:

测试数据有多组，处理到文件尾。每组测试数据第一行输入一个整数n（1≤n≤100），第二行输入n个整数。

输出格式:

对于每组测试，输出若干行，每行是一趟排序后的结果，每行的每两个数据之间留一个空格。

输入样例:

4

8 7 2 1

输出样例:

7 1 2 8

2 1 7 8

1 2 7 8

来源：

[1] 黄龙军, 等. 数据结构与算法, 上海:上海交通大学出版社, 2022.7. ISBN: 9787313269881
[2] 黄龙军, 等. 数据结构与算法（Python版）, 上海: 上海交通大学出版社, 2023. （In Press）

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

参考代码：C++（g++）

#include

using namespace std;

int a[105], n;

void print(){

    cout<

    for (int i=2;i<=n;i++)

        cout<<" "<

    cout<

}

void sift(int k, int end){

    int i=k,j=2*i;

    while(j<=end){

        if(j

        if(a[i]

        i=j;

        j=2*i;

    }

}

void heapsort(int n){

    for(int k=n/2;k>=1;k--)

        sift(k,n);

    for(int k=1;k

        swap(a[1],a[n-k+1]);

        sift(1,n-k);

        print();

    }

}

int main(){

    while (~scanf("%d", &n)){

        for (int i = 1; i <= n; i++)

            scanf("%d", &a[i]);

        heapsort(n);

    }

}

7-8 石子合并

作者 杜祥军

单位 青岛大学

由n堆石子排成一排，其编号为1，2，3……，n。每堆石子有一定的质量mi(mi<=1000),现在要将这n堆石子合并成一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，由于合并顺序的不同，导致合并成一堆石子的总代价也不同，请求出最少的代价将所有石子合并为一堆。

输入格式:

第一行输入n。
第二行输入n个mi。

输出格式:

输出一个整数，表示石子合并的最小代价。

输入样例:

4

2 5 3 1

输出样例:

22

代码长度限制

16 KB

时间限制

1000 ms

内存限制

64 MB

参考代码：C++（g++）

#include
using namespace std;
const int INF = 100000;
const int N = 205;
int Min[N][N], Max[N][N], s[N][N];//求最小、最大值
int sum[N];//计算前i堆石子的数量总和，sum[0]=0，w(i,j)=sum[j]-sum[i-1]
int a[N];//记录各堆石子的数量
int minn, maxx;
void get_Min(int n) {for (int v = 2; v <= n; v++) {//枚举合并的堆数规模for (int i = 1; i <= n - v + 1; i++) {int j = i + v - 1;int tmp = sum[j] - sum[i - 1];int i1 = s[i][j - 1] > i ? s[i][j - 1] : i;int j1 = s[i + 1][j] < j ? s[i + 1][j] : j;Min[i][j] = Min[i][i1] + Min[i1 + 1][j];s[i][j] = i1;for (int k = i1 + 1; k <= j1; k++) {if (Min[i][k] + Min[k + 1][j] < Min[i][j]) {Min[i][j] = Min[i][k] + Min[k + 1][j];s[i][j] = k;}}Min[i][j] += tmp;}}
}
void straight(int a[], int n) {for (int i = 1; i <= n; i++) {//初始化Min[i][i] = 0, Max[i][i] = 0, s[i][i] = 0;}sum[0] = 0;for (int i = 1; i <= n; i++) {sum[i] = sum[i - 1] + a[i];}get_Min(n);
}
int main(){int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}straight(a, n);cout << Min[1][n];return 0;
}

7-9 第k小

作者 严华云

单位 湖州师范学院

有n个数，求第k小的数。例如在数：{1 3 5 7 9 8 4 2 6 10}中，第3小的数是3 。

输入格式:

第一行输入两个数，n和k（n<=1000000），分别表示总的n个数和求第k小的数。第二行输入n个数( 最大数<10^7)。

输出格式:

一个数，表示第k小的数。

输入样例:

在这里给出一组输入。例如：

10 3

1 3 5 7 9 8 4 2 6 10

输出样例:

在这里给出相应的输出。例如：

3

代码长度限制

16 KB

时间限制

300 ms

内存限制

64 MB

参考代码：c++（g++）

#include 
using namespace std;
int a[1000005];
int main(){int n,k;while(~scanf("%d %d",&n,&k)){for (int i=0;i

#include 
using namespace std;
int n;
void print(int *arr){for(int i=0;i right)return;  //首先判断一下传递进来的left和right合不合理int i = left,j = right;    //把left和right赋值给i，j作为他们的初始状态int pivot = arr[left];  //让最左边的元素作为支点pivot//不是0开始，要递归调用，比如pivot右边的子数组初始下标就不是0，所以不是arr[0]while (i < j){  //i与j碰到时，结束一次排序，所以i= pivot && i < j)j--;  //j（R)要找的是小于pivot的数，所以当arr[j]>=pivot时，此数不用操作，j向左移动（别忘了i>n;int arr[n]; for(int i=0;i