C++ 排序问题

Jason_ 发布于 2020-03-25 20:57， 1620 次点击

题目描述
输入 n 及 n 个正整数，按从大到小的顺序输出。
输入
共二行
第一行只有一个正整数：n
第二行共有 n 个正整数，数与数之间有一个空格，每个数据在闭区间[100,700]内。
输出
有若干行
每行有 10 个数据，每个数据占用 4 个字符位置（最后一行可以少于 10 个数据）
样例
输入复制
5
534 657 435 556 587
输出复制
657 587 556 534 435
提示
【数据规模】
30% 的数据: 1 <= n <= 4 000
70% 的数据: 1 <= n <= 40 000
100% 的数据: 1 <= n <= 400 000
（PS：这题好像没那么简单啊，一开始直接sort，然后试了选择、冒泡都不行）

5 回复

rjsp2020-03-25 21:34

（PS：这题好像没那么简单啊，一开始直接sort，然后试了选择、冒泡都不行）

你不将你用sort的代码贴出来，别人怎么知道你代码错在哪里？

lin51616782020-03-26 10:35

每个数据在闭区间[100,700]内

这句话的意思其实就是
让你用计数排序
O(n)时间复杂度实现也非常简单
记录每一个数字出现的次数
输出的时候外层循环100到700
每个元素是多少就输出多少个下标
完事

Jason_2020-03-26 21:18

回复 2楼 rjsp

就是普通的sort然后一个cmp啊：

程序代码：

#include <bits/stdc++.h>
using namespace std;
int n,a[400001];
bool cmp(int a,int b){
    return a > b;
}
int main(){
    cin>>n;
    for (int i=1; i<=n; i++)
      cin>>a[i];
    sort(a,a+1+n,cmp);
    for(int i=0; i<n ;i++){
        cout<<a[i]<<" ";
        if ((i+1)%10==0&&i!=0) cout<<endl;
    }
    return 0;
}

40分

Jason_2020-03-26 21:22

已经解决了，居然要先输出空格再输出a[i]

就是不太知道为什么，有哪位大佬能解释一下吗？？

雪影辰风2020-04-04 15:23

回复 5楼 Jason_

这个要看评测系统了，有的评测系统对格式卡的很死