OpenJudge NOI 2.1 7213:垃圾炸弹
admin
2024-02-25 10:28:37
0次

【题目链接】

OpenJudge NOI 2.1 7213:垃圾炸弹

【题目考点】

1. 枚举

【解题思路】

解法1:枚举

可以枚举每个可能安放炸弹的位置,路口一共有1024∗1024≈1061024*1024\approx 10^61024∗1024≈106个

根据题意,当爆炸威力为d时,冲击波范围是个正方形,其边长为2d+12d+12d+1。
我们考虑当炸弹威力d为最大值50时,冲击波波及的正方形边长为2∗50+1=1012*50+1=1012∗50+1=101,这个范围内的位置有1012≈104101^2\approx 10^41012≈104个。
如果先枚举安放炸弹的位置,再枚举该炸弹波及的范围内的每个位置看这个位置有没有垃圾,那么总体复杂度会达到O(106∗104)=O(1010)O(10^6*10^4)=O(10^{10})O(106∗104)=O(1010),超过了O(107)O(10^7)O(107),是不可接受的。

考虑到有垃圾路口的数量n很小,最大值为20。那么我们在确定安放炸弹的位置后,枚举每个垃圾路口,看哪些垃圾路口在该炸弹的波及范围之内,将能被波及到的垃圾数量加和,即为在这里安装炸弹能销毁的垃圾数量。
枚举所有可以安放炸弹的位置:

  • 如果找到一个位置安放炸弹销毁的垃圾数量大于当前已知的最大垃圾销毁数量,那么可以安放炸弹的地点数量变为1。
  • 如果找到一个位置安放炸弹销毁的垃圾数量与当前已知最大垃圾销毁数量相同,那么可以安放炸弹的地点数量加1。

判断垃圾路口(i,j)是否在放在(x,y)位置的威力为d的炸弹波及范围内的方法:
垃圾路口在横向与纵向到(x,y)的距离都不能超过d。
即i与x的差值的绝对值要小于等于d,,同时j与y差值的绝对值要小于等于d,用代码表示为:abs(i-x)<= d && abs(j-y) <= d

【题解代码】

解法1:枚举

#include
using namespace std;
#define N 1030
struct Garbage
{int x, y, i;//(x,y)处有垃圾数量i	
}g[25];//g[i]:第i个垃圾路口 
int main()
{int d, n, mxSum = 0, ct;//mxSum:最大销毁垃圾数目 ct:可以销毁mxSum数量垃圾的炸弹安放位置数 cin >> d >> n;for(int i = 1; i <= n; ++i)cin >> g[i].x >> g[i].y >> g[i].i;		for(int i = 0; i <= 1024; ++i)for(int j = 0; j <= 1024; ++j){//在(i,j)位置放炸弹int sum = 0;//在(i,j)位置安放炸弹销毁的垃圾总和  for(int k = 1; k <= n; ++k)//看垃圾路口g[k]是否在(i,j)炸弹的范围之内 if(abs(i-g[k].x) <= d && abs(j-g[k].y) <= d)sum += g[k].i;if(sum > mxSum){mxSum = sum;//最大销毁垃圾数量ct = 1;//能销毁mxSum的炸弹位置变为1 }	else if(sum == mxSum)ct++;//能销毁mxSum的炸弹位置增加1}cout << ct << ' ' << mxSum;return 0;
}

相关内容

热门资讯

APEC背后的中国变化 中国力... APEC为何离不开中国力量?广东又如何成为亚太合作的窗口?11月16日,南都N视频推出《APEC背后...
老药工30年守护一株钻山风 传... 老药工30年守护一株钻山风。在河南新密,老药工马伟国用三十年时间默默守护着一株珍贵的钻山风。这种药材...
日本老年人陷入“带病工作”困境... 日本老年人陷入“带病工作”困境 养老金不足加剧问题。日本是一个高度老龄化的国家,与我们这边有所不同。...
亚马尔事件反转,央视发文:西甲... 11月16日,有媒体报道称,西甲巴塞罗那俱乐部球员亚马尔在个人社交平台账号转发一条短视频,因该视频含...
DeepSeek对App与网页... 据报道,DeepSeek 对其应用程序和网页版的长对话功能实施了使用限额。用户收到提示称,由于算力不...
中央气象台发布大风蓝色预警 多... 预计11月17日08时至18日08时,青海北部、甘肃大部、内蒙古大部、宁夏、陕西北部、山西、河北北部...
景区招保洁参照公务员体检标准 ... 景区招保洁参照公务员体检标准!近日,某景区招聘53名派遣保洁人员的消息引起了关注。招聘信息显示,应聘...
氯化铵市场年内罕见快速上涨 创... 氯化铵市场正经历一轮年内罕见的快速上涨。截至11月16日,氯化铵工业级价格达到730元/吨,创下年内...
19岁留学生在泰被成功解救 警... 泰国警方于11月14日在芭提雅一家酒店内找到一名19岁的中国留学生,所幸他身体没有受到伤害。此前,有...
女子在KTV电梯内遭陌生男子搂... 11月11日晚上11点,海口一名年轻女子走进KTV电梯,准备去三楼找朋友唱歌。她全程没沾过酒,脑子清...
凯特患癌后首次陪同威廉出访 抗... 凯特患癌后首次陪同威廉出访。2024年3月,凯特王妃证实自己得了癌症,正在接受预防性化疗。同年9月,...
“全程只服一次”流感新药纳入医... 中国疾控中心监测显示,秋冬流感流行季已逐渐开启。患上流感后高烧酸痛令人难受,传统抗流感药往往需要连续...
别让“今天就整改”成了一句客套... 别让“今天就整改”成了一句客套话。一句“今天就整改”,一个月过去,那块水泥还压在原地。这不是工作不力...
留学生遭诱骗至泰国被解救 跨境... 一名19岁的中国留学生入境泰国不到一天,就被跨国电信诈骗团伙控制。家属收到勒索视频后,中泰有关部门迅...
平价羽绒服为啥集体断货 中产过... 平价羽绒服为啥集体断货 中产过冬新宠引发抢购热潮。这个冬天,仓储式会员超市的羽绒服成了中产过冬的新宠...
大范围雨雪天气来袭 收下安全出... 今天冷空气继续影响长江以北大部分地区,预计将迎来降温。明后两天(17日至18日),冷空气势力将进一步...
柴油发电机订单排到明年年底 需... 近年来,国内数据中心和智算中心的建设加速,对大功率柴油发电机组的需求显著增加。据行业预测,到2026...
中小学幼儿园将聘任健康副校(园... 中小学校、幼儿园将聘任健康副校(园)长,由医疗卫生机构选派。国家卫生健康委、教育部、国家中医药局、国...
上海地铁开启“老人机模式” 更... 近日,不少网友注意到上海地铁的一些站点进行了升级,变得更加友好,尤其是对老年乘客。中山公园站和江苏路...
男子拆攒了18年的红包拆了3小... 最近,广东一位男子一次性拆开了攒了18年的红包,整整花了3个小时,最终清点出8523元。这一事件在评...