Acwing.4736步行者（模拟）

题目

约翰参加了一场步行比赛。

比赛为期 N 天，参赛者共 M 人（包括约翰）。

参赛者编号为 1∼M，其中约翰的编号为 P。

每个参赛者的每日步数都将被赛事方记录并公布。

每日步数最多的参赛者是当日的日冠军（可以有并列冠军）。

如果一名参赛者可以连续 N 天成为日冠军，那么他将成为创造历史的传奇冠军，这正是约翰的最终目标。

在比赛结束后，约翰拿到了所有选手的全部成绩，并试图分析自己在实现目标方面还差了多少步。

对于第 i 天，如果约翰是当日的冠军，那么他就会对当日的发挥表示满意，即当日不需要额外多走步数，如果约翰不是当日的冠军，那么他就会计算当日若要夺冠，还需要额外走的最小步数。

请你计算并输出，为了实现目标，约翰在这 N 天中需要额外走的最小总步数。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含三个整数 M,N,P。

接下来 M 行，每行包含 N 个整数，其中第 i 行第 j 个数 Si,j 表示第 i 个参赛者第 j 天的行走步数。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中 x 为组别编号（从 1 开始），y 为实现目标需要额外走的最小总步数。

数据范围

1≤T≤100,
2≤M≤1000,
1≤N≤31,
1≤P≤M,
1≤Si,j≤60000

• 输入样例1：

1
2 3 1
1000 2000 3000
1500 1500 3000
1
2
3
4

• 输出样例1：

Case #1: 500
1

样例1解释

在此样例中，比赛为期 3 天，共 2 人参赛，约翰是 1 号选手。

第 1 天，约翰若想夺冠，至少还需额外走 500 步。

后两天，约翰均为日冠军，无需额外多走步数。

所以，他一共需要额外走 500 步。

• 输入样例2：

2
3 2 3
1000 2000
1500 4000
500 4000
3 3 2
1000 2000 1000
1500 2000 1000
500 4000 1500
1
2
3
4
5
6
7
8
9

• 输出样例2：

Case #1: 1000
Case #2: 2500
1
2

样例2解释

在 Case 1 中，比赛为期 2 天，共 3 人参赛，约翰是 3 号选手。

第 1 天，约翰若想夺冠，至少还需额外走 1000 步。

第 2 天，约翰为日冠军，无需额外多走步数。

所以，他一共需要额外走 1000 步。

在 Case 2 中，比赛为期 3 天，共 3 人参赛，约翰是 2 号选手。

第 1 天，约翰为日冠军，无需额外多走步数。

第 2 天，约翰若想夺冠，至少还需额外走 2000 步。

第 3 天，约翰若想夺冠，至少还需额外走 500 步。

所以，他一共需要额外走 2500 步。

题解

#include 
using namespace std;

const int N = 32;
int ans[N];
int ap[N];

int main() {
    int t, tt;
    const int M = 1010;
    cin >> t;
    tt = t;

    while (t-- != 0) {
        int m, n, p;
        cin >> m >> n >> p;

        for (int i = 1; i <= n; i++) {
            ans[i] = 0;
            ap[i] = 0;
        }

        for (int i = 1; i <= m; i++) {
            if (i != p) {
                for (int j = 1; j <= n; j++) {
                    int temp;
                    cin >> temp;
                    ans[j] = max(ans[j], temp);
                }
            } else {
                for (int j = 1; j <= n; j++) {
                    cin >> ap[j];
                    ans[j] = max(ans[j], ap[j]);
                }
            }
        }

        int res = 0;
        for (int i = 1; i <= n; i++) {
            res += ans[i] - ap[i];
        }

        int ttt = tt - t;
        cout << "Case #" << ttt << ": " << res << endl;
    }

    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

思路

很简单的一个模拟，根据题目要求一步一步来就行了，java记得用io读取数据，不然会超时。