Boil's Blog HomeArchivesTagsCategories
算法实践2期末复习--排序
Word count: 2.6k|Reading time: 11 min

B001 快乐的蠕虫

Problem Description

有一只快乐的蠕虫居住在一个m×n大小的网格中。在网格的某些位置放置了k块石头。网格中的每个位置要么是空的，要么放置了一块石头。当蠕虫睡觉时，它在水平方向或垂直方向上躺着，把身体尽可能伸展开来。蠕虫的身躯既不能进入到放有石块的方格中，也不能伸出网格外。而且蠕虫的长度不会短于2个方格的大小。
本题的任务是给定网格，要计算蠕虫可以在多少个不同的位置躺下睡觉。

Input

输入文件的第1行是一个整数t，1<=t<=11,表示测试数据的个数。每个测试数据的第1行为3个整数：m,n和k(0<=m,n,k<=200000),接下来有k行，每行为2个整数，描述了一块石头的位置（行和列，最左上角位置为（1,1））。

Output

对每个测试数据，输出占一行，为一个整数，表示蠕虫可以躺着睡觉的不同位置的数目。

Sample Input

1
2
3
4
5
6
7
8
1
5 5 6
1 5
2 3
2 4
4 2 
4 3
5 1

Sample Output

1
9

实现思路

现按行主序排序，统计横着的，再按列主序，统计竖着的。

实现细节

1、记录每个当前位置，下一次就比较下一个石头和这个位置是否满足条件

2、开始时now置为1，而最后不要判断行/列末是否满足条件

代码

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
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
struct sto
{
    int x;
    int y;
};
sto a[200010];
bool cmp1(sto cc,sto dd)
{
    if (cc.x == dd.x)
        return cc.y<dd.y;
    else return cc.x < dd.x;
}
bool cmp2(sto cc,sto dd)
{
    if (cc.y == dd.y)
        return cc.x<dd.x;
    else return cc.y < dd.y;
}
int main()
{
    int t,m,n,k;
    ll ret;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d%d",&m,&n,&k);
        for (int i=1;i<=k;i++)
            scanf("%d%d",&a[i].x,&a[i].y);
        ret =0;
        sort(a+1,a+k+1,cmp1);
        int now=1;
        sto pre;
        pre.x =1; pre.y =1;
        for (int i=1;i<=m;i++)
        {
            if (a[now].x>i)
            {
                ret++;
                continue;
            }
            pre.x = i; pre.y =1;
            while (1)
            {
                if (a[now].y-pre.y >= 2)
                    ret++;
                pre.y = a[now].y+1;
                now++;
                if (a[now].x!=i || pre.y>n)
                    break;
            }
            if (n-a[now-1].y >=2)
                ret++;
        }
        sort(a+1,a+k+1,cmp2);
        pre.x =1; pre.y =1;
        now=1;
        for (int i=1;i<=n;i++)
        {
            if (a[now].y>i)
            {
                ret++;
                continue;
            }
            pre.y = i; pre.x =1;
            while (1)
            {
                if (a[now].x-pre.x >= 2)
                    ret++;
                pre.x = a[now].x+1;
                now++;
                if (a[now].y!=i || pre.x>m)
                    break;
            }
            if (m-a[now-1].x >=2)
                ret++;
        }
        cout << ret << endl;
    }
}

B003 英文姓名排序

Problem Description

在汉语里，对汉语姓名可以按拼音排序，也可以按笔画顺序排序。在英语里，对英语姓名主要按字母顺序排序。本题要求给定的一组英文姓名按长短顺序排序。

Input

输入文件中包含多个测试数据。每个测试数据的第1行是一个正整数N（0 < N < 100），表示该测试数据中英文姓名的数目；接下来有N行，每行为一个英文姓名，姓名中允许出现的字符有大小写英文字母、空格和点号（.），每个英文姓名长度至少为2、但不超过50.N=0表示输入结束。

Output

对输入文件中的每个测试数据，输出排序后的姓名。排序方法为：先按姓名长度从长到短的顺序排序，对长度相同的姓名，则按字母顺序排序。每2个测试数据的输出之间输出一个空行。

Sample Input

1
2
3
4
5
6
4
David A. Forsyth
Jean Ponce
Tom M. Mitchell
Thomas H. Cormen
0

Sample Output

1
2
3
4
David A. Forsyth
Thomas H. Cormen
Tom M. Mitchell
Jean Ponce

实现思路

简单的排序

##实现细节

1、这里有好多坑点，首先是长度小于2要忽略，并且最后有效的记录条数依旧是n

2、注意cmp函数里strcmp的使用

3、注意第一个n输入之后把回车符get掉

代码

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
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
struct nam
{
    char na[55];
    int len;
    int no;
};
nam a[110];
char tem[55];
bool cmp(nam x,nam y)
{
    if (x.len == y.len && strcmp(x.na, y.na)==0)
        return x.no<y.no;
    bool kk;
    if(strcmp(x.na, y.na)<0)
        kk=true;
    else kk=false;
    if (x.len == y.len)
        return kk;
    return x.len > y.len;
}
int main()
{
    int n;
    while (cin >> n)
    {
        if (n==0)
            break;
        getchar();
        for (int i=1;i<=n;i++)
        {
            gets(tem);
            int kk= strlen(tem);
            if (kk <2 || kk>50)
            {
                i--;
                continue;
            }
            strcpy(a[i].na,tem);
            a[i].len = kk;
            a[i].no = i;
        }
        sort(a+1,a+n+1,cmp);
        for (int i=1;i<=n;i++)
            cout << a[i].na << endl;
    }
}

B004 DNA排序

Problem Description

一个序列的逆序数定义为序列中无序元素对的数目。例如，在字符序列DAABEC中，逆序数为5，因为字符D比它右边的4个字符大，而字符E比它右边的1个字符大。字符序列AACEDGG只有1个逆序，即E和D,它几乎是已经排好序的，而字符序列“ZWQM”有6个逆序，它是最大程度的无序，即有序序列的逆序。
在本题中，你的任务是对DNA字符串（只包含字符“A”、“C”，“G”和“T”）进行排序。注意不是按照字母顺序，而是按照逆序数从低到高进行排序，所有字符串的长度都一样。

Input

输入文件中包含多组测试数据。每组测试数据的格式为：第1行为2个整数，正整数n(0 < n <= 50，表示字符串的长度)和正整数m(1 < m <= 100,表示字符串的数目)；然后是m行，每一行为一个字符串，长度为n。

Output

对应到输入文件中的N组测试数据，输出也有N组，每2组输出之间有一个空行。对每组输入数据，按逆序数从低到高输出各字符串，如果2个字符串的逆序数一行，则按输入时的先后顺序输出。

Sample Input

1
2
3
4
5
6
10 5
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

Sample Output

1
2
3
4
5
CCCGGGGGGA
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

##实现思路

暴力求解逆序数排序

实现细节

注意字符串从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
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
struct seq
{
    char v[55];
    int rev;
    int no;
};
seq a[110];
bool cmp(seq x,seq y)
{
    if (x.rev == y.rev)
        return x.no < y.no;
    else return x.rev < y.rev;
}
int main()
{
    int n,m;
    bool flag = false;
    while (cin >> n >> m)
    {
        if (flag) cout << endl;
        else flag =true;
        for (int i=1;i<=m;i++)
        {
            scanf("%s",a[i].v);
            a[i].rev = 0; a[i].no=i;
            for (int j=0;j<=n-2;j++)
                for (int k=j+1;k<=n-1;k++)
                    if (a[i].v[j] > a[i].v[k])
                        a[i].rev++;
        }
        sort(a+1,a+m+1,cmp);
        for (int i=1;i<=m;i++)
            cout << a[i].v << endl;
    }
}

B005 体重排序

Problem Description

作为一台很受欢迎的脱口秀节目的主持人，你正在做一期关于节食的节目。你的嘉宾是Kevorkian博士。他最近推出了一项减肥计划“Do You Want To Diet?”，这项计划向它的用户保证每天减肥1磅。
节目录制那天，你准备让一些使用Kevorkian博士减肥计划的节食者上台秀一下。你准备按他们的体重的递减顺序来安排他们出场的先后顺序。问题是他们报名时只提供了以下信息：姓名，节食的天数，节食前的体重。你要根据他们节食的天数来计算他们现在的体重。所有的节食者每天减肥1磅。

Input

输入文件包含至多100个测试数据。测试数据之间没有空行。每个测试数据包含3部分：
第1行为START；
接下来为节食者列表：包含110行，每行描述一名节食者，包括姓名、节食的天数和节食前的体重。其中姓名为120个数字、字母字符组成的字符串；节食的天数不超过1000天；节食前的体重不超过10,000。
最后一行为END。

Output

对每个测试数据，根据各节食者现在体重的递减顺序列出节食者的名字，每个节食者的名字占一行。每2个测试数据的输出之间有一个空行。

Sample Input

1
2
3
4
5
6
7
8
START
Joe 10 110
END
START
James 100 150
Laura 100 140
Hershey 100 130
END

Sample Output

1
2
3
4
5
Joe

James
Laura
Hershey

##实现思路

最简单的排序

实现细节

注意格式即可

代码

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
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
struct peo
{
    char name[25];
    int wei;
    int no;
};
peo a[100];
bool cmp(peo x,peo y)
{
    if (x.wei==y.wei)
        return x.no < y.no;
    else return x.wei > y.wei;
}
int main()
{
    char st1[10];
    bool flag =false;
    while (cin >> st1)
    {
        if (flag) cout << endl;
        else flag =true;
        int co=0,d,w;
        while (1)
        {
            cin >> a[++co].name;
            if (a[co].name[0]=='E' && a[co].name[1]=='N' && a[co].name[2]=='D')
            {
                co--;
                break;
            }
            cin >> d >> w;
            a[co].wei = w-d;
            a[co].no = co;
        }
        sort(a+1,a+co+1,cmp);
        for (int i=1;i<=co;i++)
            cout << a[i].name << endl;
    }
}

##

Author: YihangBao
Link: https://roarboil.github.io/2019/12/15/algpra/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.