第五章 完善程序

第一课 数组

【NOIP2013】序列重排

全局数组变量a定义如下：

  1. const int SIZE=100; 
  2. 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²)、空间复杂度为O(1)的算法：

  1. void swap2(int p){
  2.     int i,j,temp;
  3.     for (i=p+1;i<=n;i++){
  4.         temp=a[i];
  5.         for (j=i;j>=i-p+1;j--) a[j]=a[j-1];
  6.         a[i-p]=temp;
  7.     }
  8. }

第五章 完善程序 - 图1

事实上，还有一种更好的算法，时间复杂度为O(n)、空间复杂度为O(1)：

  1. void swap3(int p){
  2.     int start1, end1, start2, end2, i, j, temp;
  3.     start1 = 1;
  4.     end1 = p;
  5.     start2 = p + 1;
  6.     end2 = n;
  7.     while (true) {
  8.         i = start1;
  9.         j = start2;
  10.         while ((i <= end1) && (j <= end2)) {
  11.             temp = a[i];
  12.             a[i] = a[j];
  13.             a[j] = temp;
  14.             i++;
  15.             j++;
  16.         }
  17.         if (i <= end1)
  18.             start1 = i;
  19.         else if (④) {
  20.             start1 =⑤;
  21.             end1 =⑥;
  22.             start2 = j;
  23.         }else
  24.             break;
  25.     }
  26. }

④⑤⑥处应填什么呢？

【NOIP2014】最大子矩阵和

给出 m行 n列的整数矩阵，求最大的子矩阵和(子矩阵不能为空)。 输入第一行包含两个整数 m和 n，即矩阵的行数和列数。之后 m行，每行 n个整数，描述整个矩阵。程序最终输出最大的子矩阵和。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int SIZE=100;
  4. int matrix[SIZE+1][SIZE+1];
  5. int rowsum[SIZE+1][SIZE+1];
  6. // rowsum[i][j]记录第i行前j个数的和
  7. int m,n,i,j,first,last,area,ans;
  8. int main(){
  9.     cin>>m>>n;
  10.     for (i=1;i<=m;i++){
  11.         for (j=1;j<=n;j++) cin>>matrix[i][j];
  12.     }
  13.     ans=matrix[1][1];
  14.     for (i=1;i<=m;i++) rowsum[i][0]=0;
  15.     for (i=1;i<=m;i++){
  16.         for (j=1;j<=n;j++) rowsum[i][j]=rowsum[i][j-1]+matrix[i][j];
  17.     }
  18.     for (first=1;first<=n;first++){
  19.         for (last=first;last<=n;last++){
  20.             area=0;
  21.             for (i=1;i<=m;i++){
  22.                 area+=rowsum[i][last]-rowsum[i][first-1];
  23.                 if (area>ans) ans=area;
  24.                 if (area<0) area=0;
  25.             }
  26.         }
  27.     }
  28.     cout<<ans<<endl;
  29.     return 0;
  30. }