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

相关内容

热门资讯

还在说安卓系统卡,原因分析与优... 亲爱的手机控们,你们是不是还在为安卓手机卡顿的问题而烦恼呢?别急,今天我就来给你们揭秘安卓手机卡顿的...
安卓系统麻将考级软件,助力玩家... 你有没有想过,在闲暇之余,不仅能玩玩麻将,还能通过它来提升自己的技艺呢?现在,就有一款神奇的安卓系统...
安卓系统要绿色上网,安全畅游网... 亲爱的手机控们,你们有没有发现,现在上网可是越来越讲究绿色健康啦!没错,我说的就是安卓系统要绿色上网...
cf苹果转换安卓系统,苹果转安... 亲爱的游戏迷们,你们有没有想过,有一天,你的CF苹果账号里的英雄角色,能像变魔术一样,跳到安卓手机上...
安卓系统最后期限,重塑生态格局 你知道吗?最近安卓系统可是闹出了不小的风波,谷歌竟然给安卓系统定了个最后期限!这可真是让人大跌眼镜,...
安卓系统手机如何挂机,轻松实现... 亲爱的手机控们,你是否有过这样的烦恼:游戏玩到一半,突然有事要处理,手机屏幕一黑,挂机功能却没开启?...
安卓4.3系统降4.1,揭秘如... 亲爱的手机控们,你们有没有遇到过这样的情况:手机系统升级后,发现新版本的各种新功能让你眼花缭乱,但同...
系统和安卓系统有什么不同,系统... 你有没有想过,为什么你的手机和电脑有时候会表现得那么不一样呢?其实,这一切都源于它们背后的操作系统—...
麒麟系统属于安卓系统吗,并非纯... 你有没有想过,咱们平时用的手机操作系统,其实背后还有不少故事呢?比如,麒麟系统,它是不是安卓系统呢?...
哥斯拉安卓导航系统,哥斯拉安卓... 你有没有发现,现在的车载导航系统越来越智能了?就像科幻电影里的高科技产品一样,让人忍不住想多了解一点...
安卓系统怎么升级13,轻松迈向... 亲爱的手机控们,你们是不是也和我一样,对安卓系统的新版本充满了期待呢?没错,就是那个让人心动的安卓1...
给安卓系统换心脏,打造流畅体验... 你知道吗?手机界的“大手术”正在进行中呢!华为的EMUI系统,就像给安卓系统换了个“心脏”,让我们的...
安卓8.1系统的蓝牙,安卓8.... 你有没有发现,自从你的安卓手机升级到了8.1系统,蓝牙功能好像变得特别不一样了呢?今天,就让我带你来...
oppo支持安卓系统吗,引领智... 你有没有想过,你的OPPO手机是不是也跟着潮流,用上了安卓系统呢?没错,OPPO手机确实属于安卓家族...
安卓手机死机系统恢复,多重方法... 手机突然死机了,是不是感觉心里慌慌的?别急,今天就来给你支几招,让你的安卓手机死机后系统恢复得快快滴...
安卓原生系统在哪里,人工智能在... 亲爱的手机控们,你是否曾梦想过拥有一部纯粹如水的安卓手机?那种不带任何修饰,只保留安卓灵魂的系统,就...
安卓系统的推特,畅享全球资讯 安卓系统的推特:探索移动通信的新前沿在数字化时代,智能手机已经成为我们生活中不可或缺的一部分。而在这...
安卓系统怎么关闭进程,轻松关闭... 手机里的安卓系统,是不是有时候感觉它就像一个超级忙碌的小蜜蜂,总是一边飞来飞去,一边还哼哧哼哧地处理...
拥挤城市安卓系统没有,安卓系统... 你有没有发现,在这个快节奏的时代,城市就像一个巨大的磁场,把人们吸引得团团转。而在这个磁场中,安卓系...
安卓6.0系统占内存,安卓6.... 亲爱的手机控们,你们有没有发现,自从升级了安卓6.0系统后,手机就像喝饱了水的小胖子,内存占用量直线...