F - Christmas Present 2 

F - Christmas Present 2

题目大意：    

 思路解析：

        因为他是顺序前往每个孩子的家，前往时必须要带一个礼物，并且最多只能带k个礼物，所以它每次前往最多k个孩子之后就要回到初始点重新出发。

        然后我们直接计算从初始点不回家顺序前往每个孩子的距离之和ans。再维护一个更新数组d[i]，更新从i回到初始点，再从初始点到i+1的额外开销。

        再维护一个额外开销总和的数组， dp[i],表示从初始点走到 i个孩子的额外开销之和。

转移方程为 dp[i] = min(dp[j]) + d[i-1]    Math.max(0,i-k)<=j<=i-1。min(dp[j])可以使用线段树维护实现。

        这样我们就可以得到从初始点到第n-1个孩子再到初始点的额外开销之和，ans + dp[n]则为最终答案。

代码实现：

import java.io.*;
import java.math.BigInteger;
import java.util.*;


public class Main {
    static int mod = 998244353;
    static double[] t = new double[200005];
    static double[] dp;
    static int n;

    public static void main(String[] args) throws IOException {
        int T = 1;
        for (int o = 0; o < T; o++) {
            n = input.nextInt();
            int k = input.nextInt();
            int X = input.nextInt();
            int Y = input.nextInt();
            int[][] xy = new int[n + 1][2];
            for (int i = 0; i < n; i++) {
                xy[i][0] = input.nextInt();
                xy[i][1] = input.nextInt();
            }
            xy[n][0] = X;
            xy[n][1] = Y;
            double ans = dist(X, Y, xy[0][0], xy[0][1]);
            double[] d = new double[n];
            for (int i = 0; i < n; i++) {
                double dir = dist(xy[i + 1][0], xy[i + 1][1], xy[i][0], xy[i][1]);
                double ret = dist(X, Y, xy[i][0], xy[i][1]) + dist(X, Y, xy[i + 1][0], xy[i + 1][1]);
                ans += dir;
                d[i] = ret - dir;
            }
            dp = new double[n + 1]; // dp[i][1][j] 表示当前已经给了i个孩子，并且在第i个位置，还能再送j个孩子
            Arrays.fill(dp, Double.MAX_VALUE);
            Arrays.fill(t, Double.MAX_VALUE);
            for (int i = 1; i <= n; i++) {
                double qre = query(Math.max(1, i - k), i-1);
                if (i - k <= 0) qre = Math.min(qre, 0);
                dp[i] = qre + d[i - 1];
                update(i, dp[i]);
            }
            ans += dp[n];
            out.printf("%.9f", ans);
        }
        out.flush();
        out.close();
        br.close();
    }

    public static int lowbit(int x) {
        return x & (-x);
    }

    public static void update(int i, double val) {
        while (i <= n) {
            t[i] = Math.min(t[i], val);
            i += lowbit(i);
        }
    }

    public static double query(int l, int r) {
        double res = Double.MAX_VALUE;
        while (r >= l) {
            res = Math.min(res, dp[r]);
            r--;
            while (r - l >= lowbit(r)) {
                res = Math.min(res, t[r]);
                r -= lowbit(r);
            }
        }
        return res;
    }

    public static double dist(int X, int Y, int x, int y) {
        return Math.sqrt((long) (X - x) * (X - x) + (long) (Y - y) * (Y - y));
    }

    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static Input input = new Input(System.in);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class Input {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Input(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            String str = null;
            try {
                str = reader.readLine();
            } catch (IOException e) {
                // TODO 自动生成的 catch 块
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public Double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }

}