【Java版oj】day06不要二

左手的ㄟ右手 2024-03-31 17:28 14阅读 0赞

**目录**

一、原题再现

二、问题分析

三、完整代码

--------------------

> ## 一、原题再现 ##
> 
> [不要二\_牛客题霸\_牛客网][Link 1]
> 
> ### 描述 ###
> 
> 二货小易有一个W\*H的网格盒子，网格的行编号为0~H-1，网格的列编号为0~W-1。每个格子至多可以放一块蛋糕，任意两块蛋糕的欧几里得距离不能等于2。  
> 对于两个格子坐标(x1,y1),(x2,y2)的欧几里得距离为:  
> ( (x1-x2) \* (x1-x2) + (y1-y2) \* (y1-y2) ) 的算术平方根  
> 小易想知道最多可以放多少块蛋糕在网格盒子里。
> 
> #### 输入描述： ####
> 
> 每组数组包含网格长宽W,H，用空格分割.(1 ≤ W、H ≤ 1000)
> 
> #### 输出描述： ####
> 
> 输出一个最多可以放的蛋糕数
> 
> 示例1
> 
> 输入：
> 
> 3 2
> 
> 输出：
> 
> 4

> ## 二、问题分析 ##
> 
> 本题的本质就是在二维数组中每个坐标去放蛋糕，一个坐标位置放了蛋糕，跟他欧几里得距离为2的位置不能放蛋糕，这个就是关键点。对于两个格子坐标(x1,y1),(x2,y2)的欧几里得距离为: ( (x1-x2) \* (x1-x2) + (y1-y2) \* (y1-y2) ) 的算术平方根。如下图：
> 
> ![8858d4ace61d4072b704ae7551275a22.png][]
> 
> ![1595a5c8330f4e278a9056b9ef88badd.png][]
> 
> 上图绿色方格即为放蛋糕的位置，四个为一组，横竖都有四种情况，关键是要处理好这些情况。
> 
> 方法一是直接找出规律，方法二是利用两个for循环。

> ## 三、完整代码 ##
> 
>     import java.util.Scanner;
>     public class Main {
>         public static void main(String[] args) {
>             Scanner in = new Scanner(System.in);
>             int h = in.nextInt();
>             int w = in.nextInt();
>             int h12Num = (w / 4) * 2 + (w % 4 < 2 ? w % 4 : 2);
>             int h34Num = (w / 4) * 2 + (w % 4 <= 2 ? 0 : 1);
>             int ans = h / 4 * (h12Num + h34Num) * 2;
>             if (h % 4 == 1) {
>                 ans += h12Num;
>             } else if (h % 4 == 2) {
>                 ans += h12Num * 2;
>             } else if (h % 4 == 3) {
>                 ans += h12Num * 2 + h34Num;
>             } else {
>     
>             }
>             System.out.println(ans);
>         }
>     }
> 
> ![f6b597429d6d493e8688a872f27c5840.png][]
> 
>     import java.util.*;
>     public class Main {
>         public static void main(String[] args) {
>             Scanner in = new Scanner(System.in);
>             int col = in.nextInt();
>             int row = in.nextInt();
>             int count = 0;
>             int[][] array = new int[row][col];
>             for (int i = 0; i < row; i++) {
>                 for (int j = 0; j < col; j++) {
>                     if (array[i][j] == 0) {
>                         count++;
>                         if (i + 2 < row) {
>                             array[i + 2][j] = 1;
>                         } 
>                         if(j + 2 < col) {
>                             array[i][j + 2] = 1;
>                         }
>                     }
>                 }
>             } 
>             System.out.println(count);
>         }
>     }
> 
> ![13c37bc91da3464d918c734b1ea4356f.png][]

--------------------

![f76ef85aebdc4c8baf605fa57e565a96.png][]

[Link 1]: https://www.nowcoder.com/practice/1183548cd48446b38da501e58d5944eb?tpId=85&&tqId=29840&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking
[8858d4ace61d4072b704ae7551275a22.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f47db5de2d274f8dafc08351f01426d1.png
[1595a5c8330f4e278a9056b9ef88badd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/d8b47310792646f5933596c6b7b5fedd.png
[f6b597429d6d493e8688a872f27c5840.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/617e82f655604a62944c51ca617f38ae.png
[13c37bc91da3464d918c734b1ea4356f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/b3be42b4f315462e851e7dabfc8bcd54.png
[f76ef85aebdc4c8baf605fa57e565a96.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/60da14fb3d0645b0aff80fbe35370772.png