【2020】百度校招Java研发工程师笔试卷（第二批）算法题

贴一下我去年9月份写的博客

三道编程题，一道数学题，两道图论，哎嘿嘿，我就是不会做，哎嘿嘿，哭了。。。

一.最小值

牛牛给度度熊出了一个数学题，牛牛给定数字n,m,k，希望度度熊能找到一组非负整数a,b满足(n−a)(m−b)≤k且a+b尽量小。

度度熊把这个问题交给了你，希望你能帮他解决。

那么做这种题目，一看就是数学题，当时我直接看了几眼没思路就跳了。没想到是线性规划方程
其实要把这个方程拆开看
k>=(n-a)(m-b)=nm-ma-nb+ab

=m(n-a)+b(a-n)

=m(n-a-b)+b(a-n+m) // 这一步是关键，如果没有想到这一步，那么后面的就更想不到了

=m(n-(a+b)) + b ((m-n) + a)

$>= m (n - (a + b))$
是不是很像初高中做的不等式。。。呵呵呵
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
           Scanner in = new Scanner(System.in);
               long n = in.nextLong();
               long m = in.nextLong();
               long k = in.nextLong(); 
               /**
               (n - k / m) >= a+ b,我们要让两数更小那个降低
               更快,那么其实让n更小，降低得会更快点,这个也是一个关键点
               */
               if(n > m) { 
                   long temp       
                   n = m;
                   m = temp;
               }
               // 所以经过上面分析，列式子可以得
               System.out.print(n - k / m);
     }
}

二.返回公司

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while(T > 0) {
            T--;
            int n =in.nextInt();
            int m = in.nextInt();
            ArrayList<Integer>[] graph = new ArrayList[n + 1];
            for(int i = 1 ;i <= n; i++) {
                graph[i] = new ArrayList<>();
            }
            for(int i = 0; i < m;i ++) {
                int a = in.nextInt();
                int b = in.nextInt();
                graph[a].add(b);
                graph[b].add(a);
            }
            List<Integer> now = graph[1];
            boolean flag = false;
            for(int i : now) { 
                List<Integer> next = graph[i];
                if(next.contains(n) || i == n) {
                    flag = true;
                    break;
                }
            }
            if(flag) { // 这个输出一定要放外面，放里面的话如果第一个不符合就会跳出来，
            // 就检测不到后面的了，相当于每次都检测第一个
                System.out.println("POSSIBLE");
            } else {
                System.out.println("IMPOSSIBLE");
            }
        }
    }
}