hihocoder58

http://hihocoder.com/contest/offers58/problems
题目1 : 最大的K-偏差排列
遍历从大到小，如果剩下的数满足条件就说明这个数就是当前位置的最佳值

import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(), k=sc.nextInt();
        int[] res=new int[1+n];
        TreeSet<Integer>left=new TreeSet<Integer>();
        boolean[] vis=new boolean[1+n];
        for(int i=1;i<=n;i++)left.add(i);
        for(int i=1;i<=n;i++) {
            int j=Math.min(i+k, n);
            while(true) {
                while(vis[j]) j--;
                boolean ok=true;
                left.remove(j);
                int q = 0;
                for(int p:left) {
                    if(Math.abs(p-(i+q+1))>k) {
                        ok = false;
                        break;
                    }
                    q ++;
                }
                if(ok) break;
                left.add(j);
                j--;
            }
            res[i]=j;
            vis[j]=true;
            left.remove(j);
        }
        for(int i=1;i<n;i++) System.out.print(res[i]+" ");
        System.out.println(res[n]);
    }
}

题目2 : 孤独的字符
就是不久前的LC contest，focus在每个字符的有效count

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] cs=sc.next().toCharArray();
        int res=0;
        Map<Character, ArrayList<Integer>>m=new HashMap<Character, ArrayList<Integer>>();
        for(int i=0;i<cs.length;i++) {
            if(!m.keySet().contains(cs[i])) {
                ArrayList<Integer> t=new ArrayList<Integer>();
                t.add(-1);
                m.put(cs[i], t);
            }
            m.get(cs[i]).add(i);
        }
        
        for(char c:m.keySet()) m.get(c).add(cs.length);
        
        for(char c:m.keySet()) {
            for(int i=1;i<m.get(c).size()-1; i++) {
                int a=m.get(c).get(i-1),b=m.get(c).get(i),d=m.get(c).get(i+1);
                res += (b-a)*(d-b);
            }
        }
        System.out.println(res);
    }
}

题目3 : 秋天来了
TODO;感觉类似于之前求最多公共interval

image.png