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;
}

相关内容

热门资讯

linux系统怎么安装安卓,L... 亲爱的Linux爱好者们,你是否曾想过在Linux系统上体验安卓的魅力?别再犹豫了,今天就来手把手教...
安卓系统微信昵称,揭秘个性与情... 亲爱的微信迷们,你们有没有想过,在微信的世界里,给自己起一个独特的昵称,是不是就像给手机换了个新衣裳...
安卓系统ping不同通,快速区... 你有没有想过,你的安卓手机里其实也藏着一个小小的网络侦探呢?没错,就是那个神秘的ping命令!今天,...
安卓车机系统2.1,智能驾驶体... 你有没有发现,现在开车出门,车机系统就像是个贴心的智能小助手,不仅能导航,还能帮你找歌、控制空调,甚...
安卓系统彻底删除软件,轻松卸载... 手机里的软件越来越多,是不是感觉内存不够用了?别急,今天就来教你怎么在安卓手机上彻底删除那些占地方又...
安卓底层系统linux,架构解... 亲爱的读者们,你是否曾好奇过,那些在我们手机上流畅运行的安卓应用,背后究竟隐藏着怎样的秘密?今天,就...
安卓子系统内存设置,安卓系统内... 你有没有发现,自从升级了Windows 11,安卓子系统成了你电脑上的新宠儿?不过,这小家伙有时候还...
安卓系统手机哪些好用,助你轻松... 你有没有想过,在这个手机当道的世界里,哪款安卓系统手机能让你爱不释手呢?别急,今天我就来给你揭秘那些...
股票顶盘系统安卓,科联系统(0... 你有没有想过,在手机上也能轻松管理你的股票投资呢?没错,现在就有这么一款神器——股票顶盘系统安卓版。...
文都系统和安卓,基于文都系统的... 探索文都系统:安卓平台上的学习新天地在这个信息爆炸的时代,学习资源无处不在,而如何高效地利用这些资源...
安卓系统存在几年了吗,十余年创... 亲爱的读者们,你们有没有想过,那个陪伴我们日常生活的安卓系统,已经存在了多久了呢?今天,就让我带你一...
电视安卓系统8.0好吗,体验升... 亲爱的电视迷们,今天咱们来聊聊一个让电视焕然一新的话题——电视安卓系统8.0。你是不是也好奇,这个新...
用电脑恢复安卓系统,数据安全无... 亲爱的手机控们,是不是觉得你的安卓手机最近有点儿“闹脾气”,不是卡顿就是闪退,甚至有时候还突然“罢工...
安卓8录制系统声音,安卓8系统... 你有没有想过,用安卓手机录个视频,还能把系统里的声音也一起录下来?这听起来是不是很酷?想象你正在玩一...
安卓系统体感游戏,引领健康娱乐... 哎呀呀,你有没有想过,在沙发上就能动起来,和游戏里的角色一起跳跳蹦蹦?现在,这不再是梦想啦!随着科技...
安卓原生系统 如何刷,从入门到... 你有没有想过,你的手机里装的那个花里胡哨的系统,其实它有个超级酷的亲戚——安卓原生系统!想象没有那些...
鸿蒙怎样还原安卓系统,操作指南... 亲爱的手机控们,你们有没有想过,有一天你的华为手机从安卓变成了鸿蒙,然后你又想把它变回安卓呢?这可不...
如何关闭安卓盲人系统,安卓手机... 亲爱的手机用户们,你们有没有遇到过这种情况:手机屏幕突然变得“聪明”起来,不管你点哪里,它都“念念有...
安卓系统怎么装win,深度解析... 你有没有想过,你的安卓手机也能变身成为Windows系统的超级战士呢?没错,就是那个我们日常办公、学...
车载安卓系统进底层,车载安卓系... 你有没有想过,你的爱车其实也可以像智能手机一样,拥有一个智能的大脑呢?没错,就是那个我们熟悉的安卓系...