C-排队

链接：https://atcoder.jp/contests/arc133/tasks/arc133_b?lang=en

来源：AtCoder Regular Contest 133

题目描述

image.png

image.png

样例一

输入

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

输出

1
2

样例二

输入

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

输出

1
3

样例三

输入

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

输出

1
6

算法描述

本题使用LIS（2）（最长上升子序列）算法求解

首先求出在数组b中所有a[i]的倍数的下标全部存子入链表中，再对子链表进行从大到小排序（这一步很关键，因为从大到小排序在进行寻找最长上升子序列时才能正确的找寻到结果）

笔者代码

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
import java.util.*;
import java.io.*;
public class Main{
    static Scanner sc = new Scanner(new BufferedInputStream(System.in));
    static int sc(){return sc.nextInt();}

    
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    
    static final int N = (int)2e5+10,P = 131,MOD = (int)1e9+7;
    static  int n;
    static int[] a = new int[N];
    static int[] b = new int[N];
    //使用h来储存各个数字的下标
    static int[] h = new int[N];
   
    static int INF= 0x3f3f3f3f;

    public static void main(String[] args) throws Exception{
        n = sc();
        for(int i = 1;i<=n;i++){a[i]=sc();}
        for(int i = 1;i<=n;i++){
            b[i]=sc();
            //记录b[i]值的下标
            h[b[i]] = i;
           // out.print(h[b[i]]+" ");
        } 
        List<Integer> list = new ArrayList();
       
        int len=0;
        int[] dp = new int[N];
        dp[0] = 0;
        for(int i = 1;i<=n;i++){
             //寻找该数的所有在b中有倍数的下标
             list.addAll(find(a[i]));
           
        }
         //进行二分求最长上升子序列，因为我们需要存储合法的序列的下标只有在下标满足上升规则的时候才能使用
         //对每个下标进行排序
         for(int i = 0;i<list.size();i++){
            //out.print(list.get(i)+" ");
            int l=0,r = len;
             while(l<r){
                 int mid = l+r+1>>1;
                 if(list.get(i)>dp[mid]){
                     l = mid;
                 }else{
                     r = mid-1;
                 }
                
             }
             len = Math.max(len,r+1);
                 
             dp[r+1] = list.get(i);
            // out.println(r+" "+len);
         }
       
        out.println(len);
        out.close();
    }
    
    public static List<Integer>find(int num){
        List<Integer> list = new ArrayList();
        //由于数字范围为1~n，所以我们在1~n范围内开始寻找
        for(int k = 1;k*num<=n;k++){
            //添加该数字的下标
            list.add(h[num*k]);
        }
        
        //从大到小排序下表链表，因为为了对后续的二分做准备
        //因为这种情况下最多会添加一个数，进入上升排列数组中。
         Collections.sort(list,(o1,o2)->o2-o1);
        return list;
    }
    
 }