美团笔试04.09

#include<iostream> using namespace std; int main() { int n, go[100010], race[100010]; cin >> n; for (int i = 1; i <= n; i++) { int temp; cin >> temp; go[temp] = i; } for (int i = 1; i <= n; i++) { cin >> race[i]; } int res = 0; for (int i = 1; i < n; i++) { for (int j = i + 1; j <= n; j++) { if (go[race[i]] > go[race[j]]) { res += 1; break; } } } cout << res; return 0; }  直接暴力，全ac

两个哈希表，一个存出发序号-号码，一个存号码-到达顺序，然后构造一个数组，下标为出发顺序，值为到达顺序，遍历数组，记录该位置之前最大的达到顺序，并和该位置达到顺序作比较，如果比最大到达位置小则结果+1，这样能ac

动态规划做的，全A了

import java.util.HashMap; import java.util.Scanner; public class Main2 {     public static void main(String[] args){         Scanner reader = new Scanner(System.in);         int n = reader.nextInt();         reader.nextLine();         String[] go = reader.nextLine().split(" ");         String[] arrive = reader.nextLine().split(" ");         HashMap<Integer,Integer> arrivedMap = new HashMap<>();         for(int i = 0; i < n;i++){             arrivedMap.put(Integer.parseInt(arrive[i]),i);         }         //  每一个数字之前出发的人最大到达index         int[] dpmax = new int[n];         int count = 0;         dpmax[0] = Integer.MIN_VALUE;         for(int i = 1; i < n;i++){             dpmax[i] = Math.max(dpmax[i - 1],arrivedMap.get(Integer.parseInt(go[i - 1])));             if(dpmax[i] > arrivedMap.get(Integer.parseInt(go[i]))){                 count++;             }         }         System.out.println(count);     } }

第三题有a出来的吗?一直超出内存限制啊。（题目：改bug）

了解了，谢谢各位大佬，我好像是对题理解有误，把索引跟到达顺序弄混了😂

你们是实习还是春招啊