超级简单排序刷题

P1271 【深基9.例1】选举学生会

#include<iostream>

int m, n, temp;
int vote[1000];

int main(){
    std::cin >> n >> m;
    for(int i = 0; i < m; i++){
        std::cin >> temp;
        vote[temp]++;
    }
    for(int i = 1; i <= n; i++){
        while(vote[i]--){
            std::cout << i << " ";
        }
    }

    return 0;
}

P1177 【模板】排序

排序题，写一个快排练练手（填进去后超时了）

查了一下资料发现经典快排是会超时的（以第一个作为标签元素）

#include<iostream>

void qsort(int a[], int left, int right){
    int i = left, j = right, key = a[i];
    //according to key, distinguish size
    while(i < j){
        while(i < j && a[j] >= key){
            j--;
        }
        a[i] = a[j];

        while(i < j && a[i] <= key){
            i++;
        }
        a[j] = a[i];
    }
    a[i] = key;
    //done one
    if((i - 1) > left){
        qsort(a, left, i - 1);
    }
    if(right > (i + 1)){
        qsort(a, i + 1, right);
    }
    return;
}
int a[200000];
int n;
int main(){ 
    scanf("%d", &n);
    for(int i = 0;i < n; i++){
        scanf("%d", &a[i]);
    }
    qsort(a, 0, n-1);

    for(int i = 0;i < n; i++){
        printf("%d ", a[i]);
    }
    return 0;
}

小改了一下还是有问题

#include<iostream>

int a[200000];
int n;
void qsort(int left, int right){
    std::swap(a[left], a[(left + right) / 2]);
    int i = left, j = right, key = a[i];
    //according to key, distinguish size
    while(i < j){
        while(i < j && a[j] >= key){
            j--;
        }
        a[i] = a[j];

        while(i < j && a[i] <= key){
            i++;
        }
        a[j] = a[i];
    }
    a[i] = key;
    //done one
    if((i - 1) > left){
        qsort(left, i - 1);
    }
    if(right > (i + 1)){
        qsort(i + 1, right);
    }
    return;
}

int main(){ 
    scanf("%d", &n);
    for(int i = 0;i < n; i++){
        scanf("%d", &a[i]);
    }
    qsort(0, n-1);

    for(int i = 0;i < n; i++){
        printf("%d ", a[i]);
    }
    return 0;
}

P1923 【深基9.例4】求第 k 小的数

这里用std输入流太慢了，会卡时间，故用scanf

本题的思路是分治，用快排原理，先随便找一个数作为中间值，然后将数依次在中间值左右排开，此时中间值的下标就是确切下标；

find函数比较中间值和k，k较小则在中间值左边部分寻找，同理右边或者相等时。

#include<iostream>
int a[5000010];

int qsort(int left, int right){
    //according to key, distinguish size
    int key = a[left];
    while(left < right){
        while(left < right && a[right] >= key){
            right--;
        }
        a[left] = a[right];
        while (left < right && a[left] <= key){
            left++;
        }      
        a[right] = a[left];
    }
    a[left] = key;
    return left;
}
int find(int left, int right, int k){
    int temp = qsort(left, right);
    if(k == temp){
        std::cout << a[k];
    }
    else if(k < temp){
        find(left, temp - 1, k);
    }
    else{
        find(temp + 1, right, k);
    }
    return 0;
}

int main(){ 
    int n, k;
    std::cin >> n >> k;
    for(int i = 0;i < n; i++){
        scanf("%d", &a[i]);
    }
    find(0, n-1, k);

    return 0;
}

P1059 [NOIP2006 普及组] 明明的随机数

用STL的一个库模板会很好写，set就是一个有序的集合，不允许出现重复元素而且会自行从小到大排序

#include<iostream>
#include<set>

int m, temp;
std::set<int> s;

int main(){
    std::cin >> m;
   
    for(int i = 0; i < m; i++){
        std::cin >> temp;
        s.insert(temp);
    }
    std::cout << s.size() << "\n";

    while(!s.empty()){
        std::cout << *s.begin() << " ";
        s.erase(s.begin()); 
    }
    return 0;
}

也可以用桶排序，这个排序的时间复杂度是n，适用于序列个数较小的排序。

桶排序的思路就是设定一个有大小的范围数组，例如此题的随机数不超过1000，于是就设置一个大小不小于1000的数组都初始化为0，然后将下标和输入数相同的元素值+1（重复时忽略），最后根据下标从小到大遍历数组，为1就输出下标，达到从小到大排序的目的。

#include<iostream>
int m, temp, cnt = 0, random[1010] = {0};

int main(){
    std::cin >> m;
   
    for(int i = 0; i < m; i++){
        std::cin >> temp;
        if(!random[temp]){
            random[temp]++;
            cnt++;  
        }
    }
    std::cout << cnt << "\n";

    for(int i = 1; i <= 1000; i++){
        if(random[i]){
            std::cout << i << " ";
        }
    }
    return 0;
}

P1093 [NOIP2007 普及组] 奖学金

设置一个结构体，在里面存储各种成绩信息。

然后写一个cmp函数来传入sort，重构比较方式。

#include<iostream>
#include<algorithm>

struct score{
    int chinese, math, english, num, sum;
}stus[310];

int number;

/*从大到小*/
bool cmp(score a, score b){
    if(a.sum > b.sum){
        return true;
    }
    else if(a.sum < b.sum){
        return false;
    }
    else{
        if(a.chinese > b.chinese){
            return true;
        }
        else if(a.chinese < b.chinese){
            return false;
        }
        else{
            if(a.num < b.num){
                return true;
            }
            else{
                return false;
            }
        }
    }
}

int main(){
    std::cin >> number;

    for(int i = 1;i <= number; i++){
        std::cin >> stus[i].chinese >> stus[i].math >> stus[i].english;
        stus[i].sum = stus[i].chinese + stus[i].math + stus[i].english;
        stus[i].num = i;
    }

    std::sort(stus + 1, stus + number + 1, cmp);

    for(int i = 1; i <=5 ; i++){
        std::cout << stus[i].num << " " << stus[i].sum << "\n";
    }

    return 0;
}

P1781 宇宙总统

和上题的思路差不多，也是重构比较函数，这里由于票数数字太大用字符串存储。

#include<iostream>
#include<algorithm>

struct person{
    int number;
    std::string votes;
}president[21];

bool cmp(person a, person b){
    if(a.votes.length() > b.votes.length()){
        return true;
    }
    else if(a.votes.length() < b.votes.length()){
        return false;
    }
    else{
        for(int i = 0;i < a.votes.length(); i++){
            if(a.votes[i] > b.votes[i]){
                break;
            }
            if(a.votes[i] < b.votes[i]){
                return false;
            }
        }
        return true;
    }
}

int main(){ 
    int n;
    std::cin >> n;
    for(int i = 1;i <= n; i++){
        std::cin >> president[i].votes;
        president[i].number = i;
    }
    std::sort(president + 1, president + n + 1, cmp);

    std::cout << president[1].number << "\n" << president[1].votes;

    return 0;
}

[USACO07DEC] Bookshelf B

很简单的题但是很长阅读理解，一开始以为是什么背包问题，呃呃。

#include<iostream>
#include<algorithm>

int cows_high[20010];
int N, B, sum = 0;
bool cmp(int a, int b){
    return a > b;
}
int main(){
    std::cin >> N >> B;
    for(int i = 1; i <= N; i++){
        std::cin >> cows_high[i];
    }
    std::sort(cows_high + 1, cows_high + N + 1, cmp);
    int i = 1;
    while(sum < B){
        sum += cows_high[i];
        i++;
    }
    std::cout << (i - 1);
    return 0;
}

车厢重组

一道冒泡排序题，输出交换的次数就好了。

#include<iostream>
#include<algorithm>

int carriages[10010];
int n, cnt = 0;

int main(){
    std::cin >> n;
    for(int i = 1; i <= n; i++){
        std::cin >> carriages[i];
    }
    for(int i = 0; i < n; i++){
        for(int j = 1; j < n - i; j++){
            if(carriages[j] > carriages[j + 1]){
                std::swap(carriages[j], carriages[j + 1]);
                cnt++ ;
            }
        }
    }
    // for(int i = 1; i <= n; i++){
    //     std::cout << carriages[i] << " ";
    // }
    // putchar('\n');
    std::cout << cnt;

    return 0;
}

欢乐的跳

计算前后差然后排序，若是从1到n-1的公差为1的等差数列，则为jolly

#include<iostream>
#include<algorithm>
#include<math.h>

int n, temp_a = 0, temp_b = 0;
int sub[1010];

int main(){
    std::cin >> n;
    for(int i = 0; i < n; i++){
        temp_b = temp_a;
        std::cin >> temp_a;
        sub[i] = fabs(temp_a - temp_b);
    }
    std::sort(sub + 1, sub + n);
    for(int i = 1; i < n; i++){
        if(sub[i] != i){
            std::cout << "Not jolly";
            return 0;
        }
    }
    std::cout << "Jolly";

    return 0;
}

P1068 [NOIP2009 普及组] 分数线划定

这题有个小坑，是先根据排名推断出分数，再根据分数划分人，我先入为主直接根据排名划分人了。

#include<iostream>
#include<algorithm>

int m = 0, n = 0;
struct per{
    int number;
    int score;
}pers[5010];
bool cmp(per a, per b){
    if(a.score > b.score){
        return true;
    }
    else if(a.score < b.score){
        return false;
    }
    else{
        return a.number < b.number;
    }
}

int main(){
    std::cin >> n >> m;
    m = m * 1.5;
    for(int i = 1; i <= n; i++){
        std::cin >> pers[i].number >> pers[i].score;
    }
    std::sort(pers + 1, pers + 1 + n, cmp);
    //找出分数线
    int i = 1, line_score = pers[m].score;
    //测算出大于分数线的人数
    while(pers[m+1].score == line_score){
        m++;
    }
    std::cout << line_score << " " << m << '\n';
    while(pers[i].score >= line_score){
        std::cout << pers[i].number << " " << pers[i].score;
        std::cout << '\n';
        i++;
    }
    return 0;
}

P5143 攀爬者

很无聊的计算题

#include<iostream>
#include<algorithm>
#include<math.h>

int n;
double temp, sum = 0, x, y, z;
struct point{
    int x, y, z;
}points[50010];

bool cmp(point a, point b){
    return a.z < b.z;
}

int main(){
    std::cin >> n;
    for(int i = 1; i <= n; i++){
        std::cin >> points[i].x >> points[i].y >> points[i].z;
    }
    std::sort(points + 1, points + 1 + n, cmp);
    for(int i = 1; i < n; i++){
        x = pow((points[i].x - points[i+1].x), 2);
        y = pow((points[i].y - points[i+1].y), 2);
        z = pow((points[i].z - points[i+1].z), 2);
        temp = sqrt(x + y + z);
        sum += temp;
    }
    printf("%.3lf", sum);
    return 0;
}

P1012 [NOIP1998 提高组] 拼数

一开始以为是从大到小排个序然后组合，后来发现是按照高位优先排序的。

正常来说把数字看成字符串然后遍历比较排序就好了。

有个特殊情况就是，两个数的前几项都相同，比如321 和 32，组合成32321时大

但是329 和 32 则是组成 32932比较大，究其原因就是长的那个数最后一项是否大于短的那个数的第一项，若是则长的数较大，反之，由于长短数的第一项相同，直接比较长数的第一项和最后一项就好了。

#include<iostream>
#include<algorithm>

int n;
std::string a[25];
bool cmp(std::string a, std::string b){
    int len_a = a.length(), len_b = b.length();
    int len = std::min(len_a, len_b);
    for(int i = 0; i < len; i++){
        if(a[i] > b[i]){
            return true;
        }
        else if(a[i] < b[i]){
            return false;
        }
    }
    if(len_a > len_b){
        //这里代表a大于b时，a的最后一项要大
        return a[len_a - 1] > a[0];
    } 
    else if(len_a < len_b){
        //这里代表a大于b时，b最后一项要小，b大于a是false，与上面相反
        return b[len_a - 1] < b[0];
    }
    else{
        return true;
    }
}
int main(){
    std::cin >> n;
    for(int i = 0;i < n; i++){
        std::cin >> a[i];
    }
    std::sort(a, a + n, cmp);
    for(int i = 0;i < n; i++){
        std::cout << a[i];
    }

    return 0;
}