20230923 小米笔试AK

先mark一下，笔试结束后发题解

===============================

t1：信号站求一个信号最大的点位

解法：维护一个101*101大小的mp，存储信号的强度，然后遍历每个信号站的radius范围内的格子，累加到mp中

import java.util.Scanner;

public class t1 {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(",");
        int n = Integer.parseInt(s[0]);
        int radius = Integer.parseInt(s[1]);
        int[][] mp = new int[101][101];
        for (int i = 0; i < n; ++i) {
            s = sc.nextLine().split(",");
            int xx = 0;
            int yy = 0;
            int pw = 0;
            try {
                xx = Integer.parseInt(s[0]);
                yy = Integer.parseInt(s[1]);
                pw = Integer.parseInt(s[2]);
            } catch (Exception e) {
                //非常奇怪，必须捕获异常，否则会只过87%
            }
            for (int x = Math.max(0, xx - radius); x <= Math.min(100, xx + radius); ++x) {
                for (int y = Math.max(0, yy - radius); y <= Math.min(100, yy + radius); ++y) {
                    int d = (x - xx) * (x - xx) + (y - yy) * (y - yy);
                    if (d > radius * radius) continue;
                    double d1 = Math.sqrt(d * 1.0);
                    mp[x][y] += (int) Math.floor((pw / (1 + d1)));
                }
            }
        }
        int x0 = 0;
        int y0 = 0;
        int maxm = 0;
        for (int i = 0; i <= 100; ++i) {
            for (int j = 0; j <= 100; ++j) {
                if (maxm < mp[i][j]) {
                    maxm = mp[i][j];
                    x0 = i;
                    y0 = j;
                }
            }
        }
        System.out.println(x0 + "," + y0);
    }
}

t2 判断工序是否合理

解法：拓扑排序

import java.util.*;

public class t2 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String[] s = sc.nextLine().split(",");
        LinkedList<Integer>[] mp = new LinkedList[n];
        for (int i = 0; i < n; ++i) {
            mp[i] = new LinkedList<>();
        }
        int[] in = new int[n];
        for (int i = 0; i < s.length; ++i) {
            String[] ss = s[i].split(":");
            int a = Integer.parseInt(ss[0]);
            int b = Integer.parseInt(ss[1]);
            mp[b].add(a);
            in[a]++;
        }
        LinkedList<Integer> que = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            if (in[i]== 0) {
                que.add(i);
            }
        }
        while (!que.isEmpty()) {
            int first = que.pollFirst();
            for (Integer next : mp[first]) {
                in[next]--;
                if (in[next] == 0) {
                    que.add(next);
                }
            }
        }
        int flag = 1;
        for (int i = 0; i < n; ++i) {
            if (in[i] != 0) {
                flag = 0;
                break;
            }
        }
        System.out.println(flag);
    }
}