http://hihocoder.com/contest/offers48/problems
题目1 : 折线中点
二分查找

package l481;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[]xs=new int[n], ys=new int[n];
        for(int i=0;i<n;i++){
            xs[i]=sc.nextInt();
            ys[i]=sc.nextInt();
        }
        
        double[] ds=new double[n-1];
        for(int i=1;i<n;i++) {
            ds[i-1]=Math.sqrt((xs[i]-xs[i-1])*(xs[i]-xs[i-1])+(ys[i]-ys[i-1])*(ys[i]-ys[i-1]));
        }
        
        double[] sum=new double[n-1];
        sum[0]=ds[0];
        for(int i=1;i<n-1;i++) sum[i]=sum[i-1]+ds[i];
        
        int idx=-Arrays.binarySearch(sum, sum[n-2]/2)-1;
        int sx=xs[idx],tx=xs[idx+1], sy=ys[idx],ty=ys[idx+1];
        double t=sum[n-2]/2-(idx==0?0:sum[idx-1]);
        double p=t/ds[idx];
        System.out.printf("%.1f %.1f", sx+p*(tx-sx), sy+p*(ty-sy));
    }
}

题目2 : 最小先序遍历
递归

package l482;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[]a=new int[n];
        for(int i=0;i<n;i++)a[i]=sc.nextInt();
        
        int[] b=get(a, 0, n-1);
        for(int i:b) System.out.println(i);
    }

    private static int[] get(int[] a, int i, int j) {
        if(i>j)  return new int[]{};
        if(i==j) return new int[]{a[i]};
        
        int min=a[i],idx=i;
        for(int k=i+1;k<=j;k++) {
            if(a[k]<min) {
                min=a[k];
                idx=k;
            }
        }
        
        int[]l = get(a,i,idx-1);
        int[]r = get(a,idx+1,j);
        int[]res = new int[j-i+1];
        res[0]=min;
        for(int k=0;k<l.length;k++)res[1+k]=l[k];
        for(int k=0;k<r.length;k++)res[l.length+1+k]=r[k];
        return res;
    }
}

题目3 : 假期计划
枚举+排列组合，WA，有大侠可以解释一下么？

image.png