压缩变换

原题链接
暴力 TLE 50分
这里用了map记录数字最后一次出现的位置。
如果用数组存的话，需要开很大，官网评测机会运行错误，很怪。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;

public class Main {

    static int N = 100010;

    static int n;
    static int[] a = new int[N];
    static int[] b = new int[N];
    static HashSet<Integer> hs = new HashSet<>();
    static HashMap<Integer,Integer> map = new HashMap<>();

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        n = Integer.parseInt(input[0]);

        input = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) 
        {
            a[i] = Integer.parseInt(input[i - 1]);
            if(map.get(a[i]) == null)
            {
                b[i] = -a[i];
                map.put(a[i], i);
            }
            else
            {
                hs.clear();
                for(int j = map.get(a[i]) + 1; j < i; j++)
                {
                    hs.add(a[j]);
                }
                b[i] = hs.size();
                map.put(a[i], i);  //别忘记更新最后出现的位置
            }
        }

        for (int i = 1; i <= n; i++) System.out.print(b[i]+" ");
    }

}

分糖果

原题链接

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {

    static int N = 110;
    static int n, res;
    static int[] a = new int[N];
    static int[] b = new int[N];
    static HashSet<Integer> hs = new HashSet<>();

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

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] input=br.readLine().split(" ");

        n = Integer.parseInt(input[0]);

        input=br.readLine().split(" ");
        for (int i = 1; i <= n; i++) 
        {
            a[i] = Integer.parseInt(input[i - 1]);
            b[i] = a[i] / 2;
        }

        while(true)
        {
            for (int i = 1; i <= n; i++) 
            {
                if(i + 1 <= n) a[i] = b[i] + b[i + 1];
                else a[i] = b[i] + b[1];
            }
            for (int i = 1; i <= n; i++) 
            {
                if(a[i] % 2 == 1)
                {
                    a[i]++;
                    res++;
                }
                b[i] = a[i] / 2;
            }

            hs.clear();
            for (int i = 1; i <= n; i++)
            {
                hs.add(a[i]);
            }
            if(hs.size() == 1) break;
        }
        System.out.println(res);
    }
}