PAT甲级——A1105 Spiral Matrix【25】

This time your job is to fill a sequence of N positive integers into a spiral matrix in non-increasing order. A spiral matrix is filled in from the first element at the upper-left corner, then move in a clockwise spiral. The matrix has m rows and n columns, where m and n satisfy the following: m×n must be equal to N; m≥n; and m−n is the minimum of all the possible values.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N. Then the next line contains Npositive integers to be filled into the spiral matrix. All the numbers are no more than 1. The numbers in a line are separated by spaces.

Output Specification:

For each test case, output the resulting matrix in m lines, each contains n numbers. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.

Sample Input:

12
37 76 20 98 76 42 53 95 60 81 58 93

Sample Output:

98 95 93
42 37 81
53 20 76
58 60 76

就是一个分块思想

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int nn, m, n;
int main()
{
    cin >> nn;
    vector<int>v(nn);
    for (int i = 0; i < nn; ++i)
        cin >> v[i];
    n = floor(sqrt(nn));//取小值
    while (nn%n!=0)n--;//找到m,n
    m = nn / n;
    vector<vector<int>>arry(m, vector<int>(n, 0));    
    sort(v.begin(), v.end(), [](int a, int b) {return a > b; });
    int lm = 0, ln = 0;//左上角
    int rm = m - 1, rn = n - 1;//右下角
    int k = 0;//使用数据的下角标
    while (lm <= rm && ln <= rn && k < nn)
    {
        if (lm == rm)//只有一行，则打印
            for (int i = ln; i <= rn; ++i)
                arry[lm][i] = v[k++];
        else if (ln == rn)//只有一列
            for (int i = lm; i <= rm; ++i)
                arry[i][ln] = v[k++];
        else
        {
            for (int i = ln; i < rn; ++i)//上行
                arry[lm][i] = v[k++];
            for(int i=lm;i<rm;++i)//右列
                arry[i][rn]= v[k++];
            for (int i = rn; i > ln; --i)//下行
                arry[rm][i] = v[k++];
            for (int i = rm; i > lm; --i)
                arry[i][ln] = v[k++];
        }
        lm++, ln++;//左上角右下移
        rm--, rn--;//右下角左上移
    }
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
            cout << arry[i][j] << (j == n - 1 ? "" : " ");
        cout << endl;
    }
    return 0;
}