P76020 整理方块 — 题解

专题： 排序与贪心
适用题目： 新生 OJ 本地题包中的 P76020，不要直接用于外站同名题。

解题思路

把所有高度放入数组，调用排序方法后输出即可。

复杂度

时间 $O(n\log n)$，额外空间取决于排序实现。

易错点

只改变排列顺序，不能更改高度值。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int cmp_ll_asc(const void *p, const void *q) {
    long long a = *(const long long *)p, b = *(const long long *)q;
    return (a > b) - (a < b);
}
int cmp_ll_desc(const void *p, const void *q) {
    long long a = *(const long long *)p, b = *(const long long *)q;
    return (b > a) - (b < a);
}

int main(void) {
    int n;scanf("%d",&n);long long *a=malloc(n*sizeof(long long));
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    qsort(a,n,sizeof(long long),cmp_ll_asc);
    for(int i=0;i<n;i++)printf("%lld%c",a[i],i==n-1?'\n':' ');
    free(a);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

template<typename T>
void putvec(const vector<T>& a) {
    for (int i = 0; i < (int)a.size(); i++) {
        if (i) cout << ' ';
        cout << a[i];
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<ll> a(n);
    for(auto&x:a)cin>>x;
    sort(a.begin(),a.end());
    putvec(a);
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。