阿祁的部落格

ZeroJudge h162 - 最少的操作數 解題心得( 題目 )

解題概念:LIS

解題方法:這題可以換個方向想，如果找最小更改次數，是不是等於找到越長且符合規則(非嚴格遞增)的序列，就等於求最好的解，所以實際上就是找LIS的長度，把總長扣掉它就是答案!時間複雜度為O(nlogn)。

Java參考程式碼 (有更好意見可留言於下方，謝謝!)

//Author:En Chi Tsung(欉恩祁)

//Date:2022/02/04

import java.io.*;

import java.util.*;

public class zjh162 {

    public static int ret,r;

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));    

    public static int[] dp=new int[100005];

    public static void main(String[] args) throws Exception{

        int n,s,L,R,M,in;

        while(true) {

            n=readint();

            if(n==0)break;//EOF

            Arrays.fill(dp,1);//初始化

            s=0;

            for(int i=0;i<n;i++) {

                in=readint();

                if(dp[s]<=in) {

                    dp[++s]=in;//比最高值還高，加入尾端

                }

                else {

                    L=1;

                    R=s;

                    while(L!=R) { //二分搜尋比它大的最小值

                        M=(L+R)/2;

                        if(in<dp[M]) {

                            R=M;

                        }

                        else {

                            L=M+1;

                        }

                    }

                    dp[L]=in; //更新LIS

                }

            }

            bw.write((n-s)+"\n"); //印出答案

        }

        bw.flush();

    }

    

    public static int readint() throws Exception { //輸入

        ret=0;

        r=br.read();

        while(r>47&&r<58) {

            ret*=10;

            ret+=(r&15);

            r=br.read();

        }

        return ret;

    }

}