备孕百度之星-8月28日

补题

星际迷航

多个点汇聚一点的结论，汇聚到中位数（不分奇偶）。汇聚到一起的结论：每个数-i,然后汇聚到中位数。

import java.util.Scanner;
import java.util.*;
class Main {
   public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    //固定两个点，移动另外一个点
    int n = input.nextInt();
    long[][] nums = new long[n][3];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 3; j++){
            nums[i][j] = input.nextInt();
        } 
    //要到达的点是中位数
    //枚举x、y、z分别为数列维度时
    long[][] ans = new long[3][2];//0为点，1为数列维度时
    for(int i = 0; i < 3; i++){
       long[] temp = new long[n];
        for(int j = 0; j < n; j++){
            temp[j] = nums[j][i];
       }
       Arrays.sort(temp);
        ans[i][0] = get1(temp);//获取到点的坐标
        ans[i][1] = get2(temp);//获取到数列的坐标
    }
    long res = Long.MAX_VALUE; //改数据范围后，也要改这里
    for(int i = 0; i < 3; i++){
        // System.out.println(ans[i][0]+"=="+ans[i][1]);
        res = Math.min(res, ans[i][1] + ans[0][0] + ans[1][0] + ans[2][0] - ans[i][0]);
    }
    System.out.println(res);
    input.close();
   }
   public static long get1(long[] temp){
       int n = temp.length;
       long res = 0;
        int t = n / 2;//中位数下标
        for(int i = 0; i < n; i++){
            res += Math.abs(temp[t] - temp[i]);
        }
       return res;
   }
   public static long get2(long[] temp){
       //获取到数列的
       int n = temp.length;
       long res = 0;
       for(int i = 0; i < n; i++) temp[i] -= (i+1);
       Arrays.sort(temp);
       return get1(temp);
   }
}

小度的规划

pass

夏日漫步

import java.util.Scanner;
import java.util.*;

class Main {
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      // BFS
      int n = in.nextInt();
      int[] nums = new int[n];
      //之前走过的就不走了
      int[] vis = new int[n];
      Arrays.fill(vis, -1);//没来过
      //预处理跳跃操作
      Map<Integer, List<Integer>> map = new HashMap();
      for(int i = 0; i < n; i++){
          nums[i] = in.nextInt();
          if(map.containsKey(nums[i])){
              map.get(nums[i]).add(i);
          }else{
              List<Integer> l = new ArrayList();
              l.add(i);
              map.put(nums[i], l);
          }
      }
    // System.out.println(map);
    Queue<Integer> queue = new ArrayDeque();
    queue.offer(0);//当前位置
    int cl = 0;
    vis[0] = 0;//当前坐标走0步
    while(!queue.isEmpty()){
        //dfs
        cl++;
        int cn = queue.size();
        for(int i = 0; i < cn; i++){
            int t = queue.poll();
            //三种走的情况
            //向后
            if(t-1 >= 0 && vis[t-1] == -1) {
                queue.offer(t-1);
                vis[t-1] = cl;
            } 
            //向前
            if(vis[t+1] == -1){
                if(t+1 == n-1){
                    System.out.println(cl);
                    return ;
                }
                queue.offer(t+1);
                vis[t+1] = cl;
            }
            //判断能不能跳跃
            if(map.get(nums[t]).get(map.get(nums[t]).size()-1) != t){//能跳
                //找跳跃的点
                int ne = 0;
                for(int j = 0; j < map.get(nums[t]).size(); j++){
                    if(map.get(nums[t]).get(j) == t){
                        ne = map.get(nums[t]).get(j+1);
                        break;
                    }
                }
                if(ne == n-1){
                    System.out.println(cl);
                    return ;
                }
                if(vis[ne] == -1){
                    queue.offer(ne);
                    vis[ne] = cl;
                }
            }
        }
    }
    in.close();
   }
}

BFS问题

怪兽

看题解写的暴力解法，有时候要根据时间限制，合理的使用暴力解法。固定两种怪兽，求解答案是否合理

import java.util.Scanner;
import java.util.*;

class Main {

   public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    // code here
    long n = in.nextInt();//头
    long q = in.nextInt();//脚
    long n1 = in.nextInt();
    long n2 = in.nextInt();
    long n3 = in.nextInt();
    long ans1 = n, ans2 = 0;//ans1为最小，ans2为最大
    int vis = 0;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= (n-i); j++){
            long cur_ans = n - i - j;//怪兽王数量
            long cur_q = q - i * n1 - j * n2;//怪兽王的脚
            if(cur_ans * n3 == cur_q){
                vis = 1;
                ans1 = Math.min(cur_ans, ans1);
                ans2 = Math.max(cur_ans, ans2);
            }
        }
    }
    if(vis == 0){
        System.out.println(-1);
    }else{
        System.out.println(ans1+" "+ans2);
    }
    in.close();
   }
}

跑步

import java.util.Scanner;
import java.util.*;

class Main {
   public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    // code here
    int n = in.nextInt();
    int[][] nums = new int[n][2];
    for(int i = 0; i < n; i++){
        nums[i][0] = in.nextInt();
        nums[i][1] = in.nextInt();
    }
    Arrays.sort(nums, (a,b)->a[0]-b[0] != 0 ? a[0]-b[0] : b[1]-a[1]);
    // for(int i = 0;i < n; i++) System.out.println(nums[i][0]+"++"+nums[i][1]);
    //找当前最慢猫
    int cur_m = n-1;
    // int cur_sum = 1;
    long res = 1;
    for(int i = n-2; i >= 0; i--){
        //追不上的情况
        if(nums[i][1] < nums[cur_m][1] || (nums[i][1] == nums[cur_m][1] && nums[i][0] != nums[cur_m][0])){
            res = Math.max(res, cur_m - i);
            cur_m = i;
        }
    }
    res = Math.max(res, cur_m + 1);//不要忘了加最前面的一组
    System.out.println(res);
    in.close();
   }
}