2020-09-09 专项强化赛--排序_http//pintia

作者：代码吟游诗人 | 2024-02-01 08:55:57

踩

http//pintia

排序算法链接：https://editor.csdn.net/md/?articleId=108480098

拼题A链接：https://pintia.cn/problem-sets/1303164128332435456/problems/type/7

7-1 模拟EXCEL排序 (25分)

https://pintia.cn/problem-sets/1303164128332435456/problems/1303164212931547136
这个题用快排会超时，所以就改用了希尔排序

#include <stdlib.h>
#include <stdio.h>
#include<string.h>
struct node
{
    int num,sc;
    char nam[10];
}st[100005];
int n;
void f1()
{
    int step=n/2,i;
    for(;step>0;step=step/2)
    {
        for(i=step;i<n;i++)
        {
            int j;
            struct node m;
            j=i-step;
            m=st[i];
            while(j>=0&&st[j].num>m.num)
            {
                st[j+step]=st[j];
                j=j-step;
            }
            st[j+step]=m;
        }
    }
}
void f2()
{
    int step=n/2,i;
    for(;step>0;step=step/2)
    {
        for(i=step;i<n;i++)
        {
           struct node m;
            int j;
            j=i-step;
            m=st[i];
            while(j>=0&&(strcmp(st[j].nam,m.nam)>0||(strcmp(st[j].nam,m.nam)==0&&st[j].num>=m.num)))
            {
                st[j+step]=st[j];
                j=j-step;
            }
            st[j+step]=m;
        }
    }
}
void f3()
{
    int step=n/2,i;
    for(;step>0;step=step/2)
    {
        for(i=step;i<n;i++)
        {
            int j;
            struct node m;
            j=i-step;
            m=st[i];
            while(j>=0&&(st[j].sc>m.sc||(st[j].sc==m.sc&&st[j].num>=m.num)))
            {
                st[j+step]=st[j];
                j=j-step;
            }
            st[j+step]=m;
        }
    }
}

int main()
{
    int c,i;
    scanf("%d%d",&n,&c);
    for(i=0;i<n;i++)
    {
        scanf("%d%s%d",&st[i].num,st[i].nam,&st[i].sc);
    }
    if(c==1)  f1();
    else if(c==2)  f2();
    else f3();
    for(i=0;i<n;i++)
    {
        printf("%06d %s %d\n",st[i].num,st[i].nam,st[i].sc);
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

7-2 魔法优惠券 (25分)

https://pintia.cn/problem-sets/1303164128332435456/problems/1303164212931547137
qsort();
快排、希尔排序就超时，
用qsort()就能A。。。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int comp(const void* num1,const void* num2)
{
	return *(int*)num2 - *(int*)num1;
}

int x[1000006],y[1000006];
int main()
{
    int n,m,i,j;
    scanf("%d",&n);
    for(i=0; i<n; i++)
    {
        scanf("%d",&x[i]);
    }
    scanf("%d",&m);
    for(i=0; i<m; i++)
    {
        scanf("%d",&y[i]);
    }
    qsort(x,n,sizeof(int),comp);
	qsort(y,m,sizeof(int),comp);
    int s=0;
    for(i=0,j=0;i<n&&j<m;i++,j++)
    {
        if(x[i]>0&&y[j]>0)
            s=s+x[i]*y[j];
    }
    for(i=n-1,j=m-1;i>=0&&j>=0;i--,j--)
    {
        if(x[i]<0&&y[j]<0)
            s=s+x[i]*y[j];
    }
    printf("%d\n",s);

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

还是上边的题的代码
这个是用C#写的C++
主要是sort（）函数

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
bool cmp(int a,int b)
{
    return a>b;
}
int x[1000006],y[1000006];
int main()
{
    int n,m,i,j;
    scanf("%d",&n);
    for(i=0; i<n; i++)
    {
        scanf("%d",&x[i]);
    }
    scanf("%d",&m);
    for(i=0; i<m; i++)
    {
        scanf("%d",&y[i]);
    }
    sort(x,x+n,cmp);
    sort(y,y+m,cmp);
    int s=0;
    for(i=0,j=0; i<n&&j<m; i++,j++)
    {
        if(x[i]>0&&y[j]>0)
            s=s+x[i]*y[j];
        else break;
    }
    for(i=n-1,j=m-1; i>=0&&j>=0; i--,j--)
    {
        if(x[i]<0&&y[j]<0)
            s=s+x[i]*y[j];
        else break;
    }
    printf("%d\n",s);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

7-4 抢红包 (25分)

https://pintia.cn/problem-sets/1303164128332435456/problems/1303164212931547136
快排+结构体

#include <stdlib.h>
#include<stdio.h>
#include <string.h>
struct node
{
    int code,num,s;
};
struct node st[10005];
void f1(int l,int r)
{
    int i=l,j=r;
    struct node key=st[i];
    if(i<j)
    {
        while(i<j)
        {
            while(i<j&&(st[j].s<key.s||(st[j].s==key.s&&st[j].num<key.num)||(st[j].s==key.s&&st[j].num==key.num&&st[j].code>=key.code))) j--;
            st[i]=st[j];
            while(i<j&&(st[i].s>key.s||(st[i].s==key.s&&st[i].num>key.num)||(st[i].s==key.s&&st[i].num==key.num&&st[i].code<=key.code))) i++;
            st[j]=st[i];
        }
        st[i]=key;
        f1(l,i-1);
        f1(i+1,r);
    }
}

int main()
{
    int n,m,i,j,x,y;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        st[i].code=i;
        st[i].s=0;
        st[i].num=0;
    }

    for(i=1;i<=n;i++)
    {
        int r=0;
        scanf("%d",&m);
        for(j=1;j<=m;j++)
        {
            scanf("%d%d",&x,&y);
            r=r+y;
            st[x].num++;
            st[x].s=st[x].s+y;
        }
        st[i].s=st[i].s-r;
    }
    f1(1,n);
    for(i=1;i<=n;i++)
    {
        double q;
        q=st[i].s*0.01;
        printf("%d %.2lf\n",st[i].code,q);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

7-5 互评成绩 (25分)

https://pintia.cn/problem-sets/1303164128332435456/problems/1303164212931547140
快排。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
double sum[10005];
void f1(int l,int r)
{
    int i=l,j=r;
    double key=sum[i];
    if(i<j)
    {
        while(i<j)
        {
            while(i<j&&sum[j]<=key) j--;
            sum[i]=sum[j];
            while(i<j&&sum[i]>=key) i++;
            sum[j]=sum[i];
        }
        sum[i]=key;
        f1(l,i-1);
        f1(i+1,r);
    }
}

int main()
{
    int k,m,i,n,j,x;
    int min,max;
    memset(sum,0,sizeof(sum));
    scanf("%d%d%d",&n,&k,&m);
    for(i=1;i<=n;i++)
    {
        min=110;max=0;
        for(j=1;j<=k;j++)
        {
            scanf("%d",&x);
            sum[i]+=x;
            if(x<min) min=x;
            if(x>max) max=x;
        }
        sum[i]=(sum[i]-min-max)*1.0/(k-2);
    }
    f1(1,n);
    for(i=m;i>=1;i--)
    {
        if(i==m) printf("%.3lf",sum[i]);
        else printf(" %.3lf",sum[i]);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

7-9 点赞狂魔 (25分)

https://pintia.cn/problem-sets/1303166995789336576/problems/1303167147216293888
C++代码：

#include <iostream>
#include <algorithm>
using namespace std;
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
struct node
{
    char a[10];
    int num;
    double pin;
};
struct node st[110];
int cmp(struct node a,struct node b)
{
    if(a.num>b.num) return a.num>b.num;
    else if(a.num==b.num) return a.pin<b.pin;
    else return false;
}
int main()
{
    int n,i,k;
    int cnt[1010];
    scanf("%d",&n);
    for(i=0; i<n; i++)
    {
        int t=1,j;
        scanf("%s%d",st[i].a,&k);
        for(j=0; j<k; j++)
        {
            scanf("%d",&cnt[j]);
        }
        sort(cnt,cnt+k);
        for(j=1;j<k;j++)
            if(cnt[j]!=cnt[j-1]) t++;
        st[i].num=t;
        st[i].pin=k*1.0/t;
    }
    sort(st,st+n,cmp);
    if(n==0) printf("- - -\n");
    else if (n==1) printf("%s - -\n",st[0].a);
    else if(n==2) printf("%s %s -\n",st[0].a,st[1].a);
    else printf("%s %s %s\n",st[0].a,st[1].a,st[2].a);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

这用了两个sort的代码没超时，用了一个的结果就超时。。。
我知道了。。
问题出在memset上时间复杂度是On 这一个memset比10^7还多。。。
错误代码：

#include <iostream>
#include <algorithm>
using namespace std;
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
struct node
{
    char a[10];
    int num;
    double pin;
};
struct node st[110];
int cmp(struct node a,struct node b)
{
    if(a.num>b.num) return a.num>b.num;
    else if(a.num==b.num) return a.pin<b.pin;
    else return false;
}
int vis[10000007];
int main()
{
    int n,i;
    scanf("%d",&n);
    for(i=0; i<n; i++)
    {
        memset(vis,0,sizeof(vis));
        int t=0,k,x,j;
        scanf("%s%d",st[i].a,&k);
        for(j=0; j<k; j++)
        {
            scanf("%d",&x);
            if(vis[x]==1) t++;
            else vis[x]++;
        }
        st[i].num=k-t;
        st[i].pin=k*1.0/(k-t);
    }
    sort(st,st+n,cmp);
    if(n==0) printf("- - -\n");
    else if (n==1) printf("%s - -\n",st[0].a);
    else if(n==2) printf("%s %s -\n",st[0].a,st[1].a);
    else printf("%s %s %s\n",st[0].a,st[1].a,st[2].a);

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

7-12 单身狗 (25分)

https://pintia.cn/problem-sets/1303166995789336576/problems/1303167147216293891
桶排序。。
这个写的还挺顺，忘了一开始为啥错了。。

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

int mapp[100005]={0};
int vis[100005]={0};
int main()
{
    int n,i,m,t=0;
    memset(mapp,-1,sizeof(mapp));
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        mapp[x]=y;
        mapp[y]=x;
    }
    scanf("%d",&m);
    for(i=0;i<m;i++)
    {
        int x;
        scanf("%d",&x);
        vis[x]=1;
        if(vis[mapp[x]]==1) t=t+2;
    }
    vis[-1]=0;
    int k=0;
    printf("%d\n",m-t);
    for(i=0;i<100000;i++)
    {
        if(vis[i]==1)
        {
            if(vis[mapp[i]]==0||mapp[i]==-1)
            {
                if(k==0)  printf("%05d",i);
                else printf(" %05d",i);
                k++;
            }
        }
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

7-13 寻找大富翁 (25分)

https://pintia.cn/problem-sets/1303166995789336576/problems/type/7
C++
sort（）函数。。。

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

bool cmp(int a,int b)
{
    return a>b;
}

int x[1000005];
int main()
{
    int i,n,m;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
    {
        scanf("%d",&x[i]);

    }
    sort(x,x+n,cmp);
    int y;
    if(n>m)  y=m;
    else y=n;
    for(i=0;i<y;i++)
    {
        if(i==0) printf ("%d",x[i]);
        else printf(" %d",x[i]);
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

7-15 PAT排名汇总 (25分)

https://pintia.cn/problem-sets/1303166995789336576/problems/1303167147216293894
这个就是把每个考点的考生排序，最后再所有考生排序，
需要注意的一点就是这个考号是13位，输出的时候需要补全：%013d

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
struct node
{
    long long int kh;
    int zzpm,kdbh,kdpm,cj;
};
bool cmp1(struct node a,struct node b)
{
    if(a.cj!=b.cj) return a.cj>b.cj;
    else return a.kh<b.kh;
}
struct node st[30500];
int main()
{
    int n,i,cnt,r,l,q,k;
    scanf("%d",&n);
    r=0;
    for(q=1;q<=n;q++)
    {
        scanf("%d",&k);
        for(i=r;i<k+r;i++)
        {
            scanf("%lld%d",&st[i].kh,&st[i].cj);
            st[i].kdbh=q;
        }
        sort(st+r,st+k+r,cmp1);
        cnt=1;
        l=1;
        st[r].kdpm=1;
        for(i=r+1;i<k+r;i++)
        {
            if(st[i].cj!=st[i-1].cj)
            {
                st[i].kdpm=cnt+l;
                cnt=cnt+l;
                l=1;
            }
            else
            {
                l++;
                st[i].kdpm=cnt;
            }
        }
        r=r+k;
    }
    sort(st,st+r,cmp1);
    cnt=1;
    l=1;
    st[0].zzpm=1;
    for(i=1;i<r;i++)
    {
        if(st[i].cj!=st[i-1].cj)
        {
            st[i].zzpm=cnt+l;
            cnt=cnt+l;
            l=1;
        }
        else
        {
            l++;
            st[i].zzpm=cnt;
        }
    }
    printf("%d\n",r);
    for(i=0;i<r;i++)
    {
        printf("%013lld %d %d %d\n",st[i].kh,st[i].zzpm,st[i].kdbh,st[i].kdpm);
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】