离散型数据

差不多就是李煜东讲的方法，其实还是参考了c++答案。。才过的。。

他视频没怎么讲题。

我有个直觉就是acw的测试数据没那么大。？因为$a_i$是可以到$1e^{9}$的 但是这样直接开数组不行。

不知道是不是我哪里不太对。。

排序 $nlgn$

Java 代码

import java.util.*;
import java.io.*;

public class Main
{
    static int N = 200010;
    static int[] langCount = new int[N], langMap = new int[N];

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        {
            int n = in.nextInt(), idx = 0;
            for(int i = 0; i < n; i++)
            {
                int lan = in.nextInt(); // language understand
                if(langMap[lan] == 0)
                {
                    langMap[lan] = ++idx;
                }
                langCount[langMap[lan]]++;
            }
            int m = in.nextInt();
            int[] b = new int[m], c = new int[m];
            int[][] ary = new int[m][3];
            // int audio = -1, sub = -1, bestmovie = -1;
            for(int i = 0; i < m; i++) b[i] = in.nextInt();   // audio
            for(int i = 0; i < m; i++) c[i] = in.nextInt();   // sub
            for(int i = 0; i < m; i++) 
            {
                int mappedLan1 = langMap[b[i]], mappedLan2 = langMap[c[i]],
                    lcount1 = langCount[mappedLan1], lcount2 = langCount[mappedLan2];
                ary[i] = new int[]{lcount1, lcount2, i + 1};
            }
            Arrays.sort(ary, (u, v)->(u[0] != v[0] ? v[0] - u[0] : v[1] - u[1]));
            System.out.println(ary[0][2]);
        }
    }
}

哈希map

$N$

这个其实没什么好说的， 很标准的hash

只不过这段我可以过cf， 过不了acw。。 就贼惨

Java 代码

import java.util.*;
import java.io.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        {
            int n = in.nextInt();
            Map<Integer, Integer> map = new HashMap<>();
            for(int i = 0; i < n; i++)
            {
                int language = in.nextInt(); // language understand
                map.put(language, map.getOrDefault(language, 0) + 1);
            }
            int m = in.nextInt();
            int[] b = new int[m], c = new int[m];
            int audio = -1, sub = -1, bestmovie = -1;
            for(int i = 0; i < m; i++) b[i] = in.nextInt();   // audio
            for(int i = 0; i < m; i++) c[i] = in.nextInt();   // sub
            for(int i = 0; i < m; i++) 
            {
                int bcount = map.getOrDefault(b[i], 0), ccount = map.getOrDefault(c[i], 0);
                if(audio < bcount)
                {
                    audio = bcount;
                    bestmovie = i + 1;
                    sub = ccount;
                }
                else if(audio == bcount)
                {
                    // same audio understanding
                    if(sub < ccount)
                    {
                        sub = ccount;
                        bestmovie = i + 1;
                    }
                }
            }
            System.out.println(bestmovie);
        }
    }
}