一、 【noip2013】序列重排
全局数组变量 a 定义如下:
const int SIZE=100;
int a[SIZE],n;
它记录着一个长度为 n 的序列 a[1] ,a[2] ,… , a[n] 。现在需要一个函数,以整数 p(1 ≤p≤ n) 为参数,
实现如下功能: 将序列 a 的前 p 个数与后 n-p 个数对调, 且不改变这 p 个数(或 n-p 个数)之间的相对位置。
例如,长度为 5 的序列 1, 2,3,4,5,当 p=2 时重排结果为 3,4, 5,1,2。
可以用时间换空间,使用时间复杂度为O(n^2)、空间复杂度为 O(1) 的算法:
#include <bits/stdc++.h>
using namespace std;
const int SIZE=100;
int a[SIZE],n;
void swap2(int p){
int i, j, temp;
for (i = p + 1;i <= n;i++) {
temp = a[i];
for (j = i;j >= (i-p+1) ; j--)
a[j] = a[j - 1];
a[i-p] = temp;
}
}
int main(){
int p;
cin >> n >> p;
for(int i = 1 ; i <= n; i++){
cin >> a[i];
}
swap2(p);
for(int i = 1 ;i <= n ; i++){
cout << a[i] << " ";
}
return 0;
}
事实上,还有一种更好的算法,时间复杂度为O(n)、空间复杂度为O(1):
void swap3(int p){
int start1, end1, start2, end2, i, j, temp;
start1 = 1;
end1 = p;
start2 = p + 1;
end2 = n;
while (true) {
i = start1;
j = start2;
while ((i <= end1) && (j <= end2)) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j++;
}
if (i <= end1)
start1 = i;
else if (④) {
start1 =⑤;
end1 =⑥;
start2 = j;
}else
break;
}
}
二、最大子矩阵和
给出 m行 n列的整数矩阵,求最大的子矩阵和(子矩阵不能为空)。 输入第一行包含两个整数 m和 n,即矩阵的行数和列数。之后 m行,每行 n个整数,描述整个矩阵。程序最终输出最大的子矩阵和。