【每日一题】不要二

忘是亡心i 2022-12-25 08:53 92阅读 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)

输出描述：

> 输出一个最多可以放的蛋糕数

输入：

> 3 2

输出：

> 4

**解题思路**  
题中关键点：( (x1-x2) \* (x1-x2) + (y1-y2) \* (y1-y2) ) 的算术平方根等于2不能放蛋糕，这里将该条件变成：( (x1-x2) \* (x1-x2) + (y1-y2) \* (y1-y2) ) ==4不能放蛋糕，等于4有以下几种情况：  
1+3=4  
3+1=4  
2+2=4  
0+4=4  
4+0=4  
显然，前3个是不可能的，因为(x1-x2) \* (x1-x2) 或 (y1-y2) \* (y1-y2)不可能等于2或3，要么等于0，要么等于4。

得出结论：满足条件x1 == x2,y1-y2 == 2或者x1-x2 == 2,y1 == y2.

**代码展示**

#include <iostream>
    #include <vector>
    using namespace std;
    
    int main()
    {
        
    	int w, h, res = 0;
    	cin >> w >> h;
    	vector<vector<int>> a;
    	a.resize(w);
    	for(auto& e : a)
    		e.resize(h, 1);
    	for(int i = 0;i < w;i++)
    	{
        
    		for(int j = 0;j < h;j++)
    		{
        
    			if(a[i][j] == 1)
    			{
        
    				res++;
    				if((i + 2) < w)
    					a[i + 2][j] = 0;
    				if((j + 2) < h)
    					a[i][j + 2] = 0;
    			}
    		}
    	}
    	cout << res << endl;
    	return 0;
    }

[Link 1]: https://www.nowcoder.com/practice/1183548cd48446b38da501e58d5944eb?tpId=85&&tqId=29840&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

发表评论取消回复

表情：

评论列表（有 0 条评论，92人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode(每日一题)-101.对称二叉树

【题目描述】给定一个二叉树，检查它是否是镜像对称的 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10

た入场券/ 2023年10月04日 11:26/ 0 赞/ 44 阅读

相关树根（每日一题）

数根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数，那么这个数就是数根；如果结果是两位数或者包括更多位的数字，那么再把这些数字加起来。如此进行下去，直到得到是

矫情吗；*/ 2023年02月26日 08:28/ 0 赞/ 103 阅读

相关【LeetCode-每日一题】-739-每日温度

1. 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG

梦里梦外;/ 2023年02月20日 02:15/ 0 赞/ 12 阅读

相关【每日一题】不要二

题目来源牛客网链接：[不要二][Link 1] 题目描述二货小易有一个W\H的网格盒子，网格的行编号为0~ H-1，网格的列编号为0~W-1。每个格子至多可

忘是亡心i/ 2022年12月25日 08:53/ 0 赞/ 93 阅读

相关 PMP每日一题

2021年8月31日 1.产品设计被认定为是各种制造问题的根本原因。若要在将来避免面对同样的问题，项目经理应该怎么做？ A.执行实施质量管理过程 B.审查质量管理计划

╰+攻爆jí腚メ/ 2022年09月11日 00:07/ 0 赞/ 1807 阅读

相关 java -- 每日一题

1. [Hashtable源码解析][Hashtable] 2. [Java面试每日一题 -- 动态代理两种方式及比较][Java_ --] 3

系统管理员/ 2022年05月27日 02:40/ 0 赞/ 255 阅读

相关编程题：不要二

题目描述二货小易有一个W\H的网格盒子，网格的行编号为0~H-1，网格的列编号为0~W-1。每个格子至多可以放一块蛋糕，任意两块蛋糕的欧几里得距离不能等于2。对于

谁借莪１个温暖的怀抱￠/ 2022年05月22日 03:25/ 0 赞/ 141 阅读

相关每日一题之 HashMap

点击上方 [Java后端][Java]，选择设为星标优质文章，及时送达 -------------------- HashMap和ConcurrentHashMap

拼搏现实的明天。/ 2021年09月02日 07:58/ 0 赞/ 491 阅读

相关每日一题之 Kafka

点击上方 [Java后端][Java]，选择设为星标优质文章，及时送达 -------------------- 为什么需要消息队列解耦，异步处理，削

墨蓝/ 2021年09月02日 06:16/ 0 赞/ 405 阅读

相关每日一题之 Spring

点击上方 [Java后端][Java]，选择设为星标优质文章，及时送达 -------------------- 什么是三级缓存 1. 第一级缓存：单

待我称王封你为后i/ 2021年09月02日 05:51/ 0 赞/ 263 阅读