奶牛体操

题目

1459. 奶牛体操 - AcWing题库

为了提高健康水平，奶牛们开始进行体操训练了！

农夫约翰选定了他最喜爱的奶牛 Bessie 来执教其他 $N$ 头奶牛，同时评估她们学习不同的体操技术的进度。

$K$ 次训练课的每一次，Bessie 都会根据 $N$ 头奶牛的表现给她们进行排名。

之后，她对这些排名的一致性产生了好奇。

称一对不同的奶牛是一致的，当且仅当其中一头奶牛在每次训练课中都表现得都比另一头要好。

请帮助 Bessie 计算一致的奶牛的对数。

输入格式

输入的第一行包含两个正整数 $K$ 和 $N$。

以下 $K$ 行每行包含整数 $1…N$ 的某种排列，表示奶牛们的排名（奶牛们用编号 $1…N$ 进行区分）。

如果在某一行中 $A$ 出现在 $B$ 之前，表示奶牛 $A$ 表现得比奶牛 $B$ 要好。

输出格式

输出一行，包含一致的奶牛的对数。

数据范围

$1≤K≤10$,
$1≤N≤20$

输入样例：

3 4
4 1 2 3
4 1 3 2
4 2 1 3

输出样例：

4

样例解释

一致的奶牛对为 $(1,4)、(2,4)、(3,4)、(1,3)$。

思路

这道题首先看数据范围，发现很小，所以这道题直接进行有关的暴力就行了，可以进行有关的优化，设$f[i][j]$表示$i$比$j$排名靠前的次数。

代码

import java.util.*;
public class Main {
    static int n, k;
    static int[][] f = new int[50][50];
    static int[] a = new int[50];
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        k = inScanner.nextInt();
        n = inScanner.nextInt();
        for(int i = 1; i <= k; i ++)
        {
            for(int j = 1; j <= n; j ++)
                a[j] = inScanner.nextInt();
            for(int j = 1; j < n; j ++)
            {
                for(int ii = j + 1; ii <= n; ii ++)
                    f[a[j]][a[ii]] ++;
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= n; j ++)
            {
                if(f[i][j] == k)
                    ans ++;
            }
        }
        System.out.println(ans);
        inScanner.close();
    }
}