This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

Problem Set Master Index Study reference blog: Data Structure Study Notes <8> Sorting

10-Sort 4 Count Work Experience (20 pts)

Problem link

Very simple exercise. Think about which sort is the most efficient here. This is a must-do.

PS: Super simple, didn't even feel like sorting it lol

Code

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 100005;
const int inf  = 0x3f3f3f;
int N, x;
int a[55];
int main(){
    cin >> N;
    for(int i = 0; i < N; ++i) {
        cin >> x;
        a[x]++;
    }
    for(int i = 0; i <= 50; ++i)
        if(a[i])
            cout << i << ":" << a[i] << endl;
    return 0;
}

Test Cases

10-Sort 5 PAT Judge (25 pts)

Problem link

2014 PAT Spring Exam real problem, for students preparing for the exam to practice.

Problem Summary

PAT's ranking list is generated from the status list, which shows submission scores. Generate the ranking list for PAT. Given N users, K problems, and M submissions, produce the final ranking. Notes:

• The ranking list must be printed in increasing order of rank.
• Users with the same total score share the same rank.
• Users with the same rank are sorted by the number of fully solved problems in descending order. If still tied, sort by their ID in increasing order.
• -1 means compilation failed, but -1 counts as 0 points rather than no submission.
• Users whose submissions all failed to compile or who never submitted must not appear in the ranking list. It is guaranteed that at least one user can be displayed.

Approach

Watch out for several pitfalls: if compilation fails there are 0 points, but the user may not necessarily appear on the ranking list, because if all problems failed to compile they cannot be displayed. However, if compilation passes with 0 points, it counts as a submission.

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 1000005;
const int inf  = 0x3f3f3f;
int N,K,M,cnt;//用户总数 问题总数 提交总数
int p[7];//p[i]表示第i个问题的满分
struct User{
    int id, sum;//id 总分
    int acnum, rank;//完全解决的数量 排名
    bool flag;//是否能显示在榜单中
    int s[7];//每个问题的分数 -1为未提交
    User():sum(0),acnum(0),flag(false) {
        for(int i = 1; i <= 6; ++i) s[i] = -2;//这里-2是为了方便比较
    }
    bool operator<(const User& u) {
        if(flag != u.flag) return flag > u.flag;
        else if(sum != u.sum) return sum > u.sum;
        else if(acnum != u.acnum) return acnum > u.acnum;
        else if(id != u.id) return id < u.id;
    }
} U[maxn];
bool cmp(User& u1, User& u2) {

}
int main(){
    cin >> N >> K >> M;
    for(int i = 1; i <= N; ++i) U[i].id = i;
    for(int i = 1; i <= K; ++i) {
        cin >> p[i];
    }
    for(int i = 0; i < M; ++i) {//每个提交
        int id, num, score;
        cin >> id >> num >> score;
        if(U[id].s[num] == p[num]) continue;
        if(score >= U[id].s[num]) {//这个提交使分数更高
            if(score == -1) //编译未通过 算零分
                U[id].s[num] = 0;
            else {
                U[id].flag = true;
                U[id].s[num] = score;
            }
        }
    }
    for(int i = 1; i <= N; ++i) {//统计ac数、总分、flag等
        for(int j = 1; j <= K; ++j) {
            if(U[i].s[j] != -2) {
                U[i].sum += U[i].s[j];
                if(U[i].s[j] == p[j]) U[i].acnum++;
            }
        }
        if(U[i].flag) //有分的才参加排名
            cnt++;
    }
    sort(U+1, U+N+1);
    U[1].rank = 1;
    for(int i = 2; i <= cnt; ++i) {
        if(U[i].sum == U[i-1].sum) {
            U[i].rank = U[i-1].rank;
        } else U[i].rank = i;
    }
    for(int i = 1; i <= cnt; ++i) {
        printf("%d %05d %d", U[i].rank, U[i].id, U[i].sum);
        for(int j = 1; j <= K; ++j) {
            if(U[i].s[j] == -2) printf(" -");
            else printf(" %d", U[i].s[j]);
        }
        printf("\n");
    }
    return 0;
}

Test Cases

10-Sort 6 Sort with Swap(0, i) (25 pts)

Problem link

2013 graduate exemption exam real problem. It requires some thinking -- once you figure it out, it becomes very easy. So take some time to think about it if you can. If you really can't figure it out, don't worry, it will be explained in the last lecture.

Couldn't solve it myself, watched Professor Chen Yue's explanation.

Problem Summary

Given a permutation of N numbers, how to achieve sorting using only swaps with 0. A permutation of N numbers consists of several independent cycles.

Approach

There are 3 types of cycles:

• Single-element cycle: Only 1 element -- no swap needed
• Cycle with n elements, including 0: Requires n-1 swaps
• Cycle with n elements, not including 0: First swap 0 into the cycle (1 swap), then perform (n+1)-1 swaps -- a total of n+1 swaps

Let there be C cycles with a total of S elements, then:

• If 0 is in a single-element cycle, all remaining cycles with n_i elements each require n_i+1 swaps. Since the sum of all n_i equals S, the total number of swaps is S+C.
• If 0 is not in a single-element cycle, one cycle requires n₀-1 swaps, and the remaining C-1 cycles with n_i elements each require n_i+1 swaps. Since the sum of all n_i equals S, the total number of swaps is S+C-1-1 = S+C-2.

Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 1000005;
const int inf  = 0x3f3f3f;
int a[maxn];//当a[i] = i是说明这个元素放对了地方
int N,S,C;//S为环中元素总数 C为环的个数
bool flag;
void swap(int& a, int& b) {
    int t = a;
    a = b;
    b = t;
}
int main(){
    cin >> N;
    for(int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    if(a[0] == 0) flag = true;
    for(int i = 0; i < N; ++i) {
        if(a[i] !=  i) {
            C++;
            while(a[i] != i) {
                swap(a[i], i);
                S++;
            }
        }
    }
    if(flag) cout << S+C << endl;
    else cout << S+C-2 << endl;
    return 0;
}

Test Cases