# Part2:作业

• 作业1

10-排序4 统计工龄（20 分）

8
10 2 0 5 7 2 5 2

0:1
2:3
5:2
7:1
10:1

#include <stdio.h>

int main(){
//年龄的桶
int a[51]={0};

//记录循环次数
int n;
scanf("%d",&n);

//记录年龄
int x;
for(int i=0;i<n;i++){
scanf("%d",&x);
a[x]++;
}

for(int i=0;i<51;i++){
if(a[i]!=0){
printf("%d:%d\n",i,a[i]);
}
}

return 0;
}
• 作业2

10-排序5 PAT Judge（25 分）
The ranklist of PAT is generated from the status list, which shows the scores of the submissions. This time you are supposed to generate the ranklist for PAT.

Input Specification:
Each input file contains one test case. For each case, the first line contains 3 positive integers, N (≤10000 ), the total number of users, K (≤5), the total number of problems, and M (≤100000 ), the total number of submissions. It is then assumed that the user id’s are 5-digit numbers from 00001 to N, and the problem id’s are from 1 to K. The next line contains K positive integers p[i] (i=1, …, K), where p[i] corresponds to the full mark of the i-th problem. Then M lines follow, each gives the information of a submission in the following format:
user_id problem_id partial_score_obtained
where partial_score_obtained is either −1 if the submission cannot even pass the compiler, or is an integer in the range [0, p[problem_id]]. All the numbers in a line are separated by a space.

Output Specification:
For each test case, you are supposed to output the ranklist in the following format:
rank user_id total_score s[1] … s[K]
where rank is calculated according to the total_score, and all the users with the same total_score obtain the same rank; and s[i] is the partial score obtained for the i-th problem. If a user has never submitted a solution for a problem, then “-“ must be printed at the corresponding position. If a user has submitted several solutions to solve one problem, then the highest score will be counted.
The ranklist must be printed in non-decreasing order of the ranks. For those who have the same rank, users must be sorted in nonincreasing order according to the number of perfectly solved problems. And if there is still a tie, then they must be printed in increasing order of their id’s. For those who has never submitted any solution that can pass the compiler, or has never submitted any solution, they must NOT be shown on the ranklist. It is guaranteed that at least one user can be shown on the ranklist.

Sample Input:
7 4 20
20 25 25 30
00002 2 12
00007 4 17
00005 1 19
00007 2 25
00005 1 20
00002 2 2
00005 1 15
00001 1 18
00004 3 25
00002 2 25
00005 3 22
00006 4 -1
00001 2 18
00002 1 20
00004 1 15
00002 4 18
00001 3 4
00001 4 2
00005 2 -1
00004 2 0

Sample Output:
1 00002 63 20 25 - 18
2 00005 42 20 0 22 -
2 00007 42 - 25 - 17
2 00001 42 18 18 4 2
5 00004 40 15 0 25 -

#include <stdio.h>
void Swap(int *a,int *b);
void PercDown( int A[], int p, int N );
void HeapSort( int A[], int N );

int main(){
const int n1=1000000;
const int n2=10000;

int n,k,m;
scanf("%d %d %d",&n,&k,&m);
//读入分值,第一个元素为0
int p[k+1]={0};
for(int i=1;i<k+1;i++){
scanf("%d",&p[i]);
}

//读入数据,增加一个维度方便后续处理
int a[n+1][k+1]={0};
//判断有没有交,如果交了则为1
int flag[n+1]={0};

for(int i=1;i<n+1;i++){
for(int j=1;j<k+1;j++){
a[i][j]=-2;
}
}

for (int i=0;i<m;i++){
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
if(z>=-1){
flag[x]=1;
}
if(z>a[x][y]){
a[x][y]=z;
}
}
//	for (int i=0;i<n+1;i++){
//		printf("%d\n",flag[i]);
//	}

//记录总分
int b[n]={0};
for (int i=1;i<n+1;i++){
//记录满分个数
int s=0;

for (int j=1;j<k+1;j++){
if(a[i][j]>0){
b[i-1]+=n1*a[i][j];
}
if(a[i][j]==p[j]){
s++;
}
}
b[i-1]+=n2*s+(n+1-i);
}
HeapSort(b,n);

int index=1;
int j=1;
int start=n-1;
int temp=b[n-1]/n1;
int s=0;

while(index<=k && j<=n){
//printf("%d\n",b[n-j]);
int i=n+1-b[n-j]%n2;
int score=b[n-j]/n1;
if (score!=temp){
index+=s;
temp=score;
s=1;
}else{
s++;
}
if(flag[i]>0){
printf("%d ",index);
if(i>=10000){
printf("%d",i);
}else if(i>=1000){
printf("0%d",i);
}else if(i>=100){
printf("00%d",i);
}else if(i>=10){
printf("000%d",i);
}else{
printf("0000%d",i);
}
printf(" %d",score);
for(int p=1;p<=k;p++){
if(a[i][p]>=0){
printf(" %d",a[i][p]);
}else if (a[i][p]==-1){
printf(" 0");
}else{
printf(" -");
}
}
printf("\n");
}
j++;
}
return 0;

}

//交换
void Swap(int *a,int *b){
int t=*a;
*a=*b;
*b=t;
}

//最大堆下滤
void PercDown( int A[], int p, int N ){
/* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
int Parent,Child,x;
x=A[p];

for(Parent=p;(2*Parent+1)<N;Parent=Child){
Child=Parent*2+1;
if((Child<N-1)&&(A[Child]<A[Child+1])){
Child++;
}
if(x>=A[Child]){
break;
}else{
A[Parent]=A[Child];
}
}
A[Parent]=x;
}

//堆排序
void HeapSort( int A[], int N ){
int i;

//从有子节点的点开始
for(i=N/2-1;i>=0;i--){
PercDown(A,i,N);
}

for(i=N-1;i>0;i--){
Swap(&A[0],&A[i]);
PercDown(A,0,i);
}
}
• 作业3

10-排序6 Sort with Swap(0, i)（25 分）
Given any permutation of the numbers {0, 1, 2,…, N−1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:
Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}
Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.

Input Specification:
Each input file contains one test case, which gives a positive N (≤100000) followed by a permutation sequence of {0, 1, …, N−1}. All the numbers in a line are separated by a space.

Output Specification:
For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input:
10
3 5 7 2 6 4 9 0 8 1

Sample Output:
9

#include <stdio.h>
void swap(int *a,int *b){
//printf("%d %d\n",*a,*b);
int temp=*a;
*a=*b;
*b=temp;
//printf("%d %d\n",*a,*b);
}

int main(){
int n;
scanf("%d",&n);

//读入数据
int a[n];
//记录a[i]!=i的元素个数
int s=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(a[i]!=i){
s++;
}
}

//交换次数
int k=0;
//首先明确一点，除了0以外，其余元素如果已经在自己的位置,那么就不会再移动了
//记录和0交换的元素的开始位置
int index=1;

while(s>0){
//0在0上，那么和第一个不在自己位置上元素交换
if(a[0]==0){
while(index<n){
if(a[index]!=index){
swap(&a[0],&a[index]);
break;
}
//下一次遍历从后一个元素开始
index++;
}
//a[i]!=i的元素个数加1
s++;
//交换次数加1
k++;
//0不在0上，不妨设a[0]=k,那么直接交换a[0]和a[k]，使得k在a[k]上
}else{
swap(&a[0],&a[a[0]]);
//如果a[0]正好为0，a[i]!=i的元素个数减少 2，否则减少1
if(a[0]==0){
s-=2;
}else{
s--;
}
//交换次数加1
k++;
}
}
printf("%d",k);
return 0;
}