描述 一个M个方格连接成的轨道上,小明在轨道的左端,在轨道的右端有一个掩体,在某一时刻,会有怪物从掩体爬出来,然后每秒种移动一格向小明逼近。小明可以在轨道左端开火,这样在轨道上的怪物都会被消灭。如果怪物出现的时间都预先知道,请问小明最少需要开火多少次才能消灭所有的怪物。#include<bits/stdc++.h> using namespace std; int n,m,x,t[1000001],o[1000001],mx,time1,end,now,gun;//找最大值可以有效提高桶排序的效率 int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>x; t[x]++;//准备 if(x>mx) { mx=x; }//提高效率 } int top=1; for(int i=1;i<=mx;i++) { while(t[i]) { o[top]=i; top++; } }//排序 time1=o[1]; end=o[1]+m-1; for(int i=1;i<=n;i++)//模拟(i为时间) { if(i==n) { gun++; break; }//怪已刷完 if(o[i]==end) { time1=o[i+1]; end=o[i+1]+m-1; gun++; }//怪到眼前 } cout<<gun; } 为什么RE?
时间: 2023-05-30 15:04:42 浏览: 176
假设怪物从掩体出现的时间为 t1, t2, ..., tn,相邻的出现时间之间的距离为 d1, d2, ..., dn-1。则小明最少需要开火 n 次。因为每次开火可以消灭在左端到当前怪物位置之间的所有怪物,而在两个相邻的怪物出现之间的时间,怪物会向小明靠近至少一格,所以无法一次开火消灭两个相邻的怪物。
相关问题
八皇后问题任意两个皇后不在同一块方格上共有几种摆法
八皇后问题是经典的回溯算法问题,其解法可以通过递归实现。
在一个8x8的棋盘上,放置8个皇后,使得任意两个皇后都不在同一行、同一列、同一对角线上。共有92种不同的解法。
如果我们把第一个皇后放在第一行的任意一个位置,那么第二个皇后就不能放在第一行的任何一个位置。同理,第三个皇后也不能放在已经放置了前两个皇后的同一行、同一列、同一对角线上,以此类推。
具体实现可以使用一个数组来记录每个皇后的位置,然后通过递归来尝试每一种放置方法,直到找到所有的解法为止。
在一个2k×2k 个方格组成的棋盘中。代码
这里是一个基本的实现,可以用来生成一个2k×2k个方格组成的棋盘。代码中使用了Python的turtle库来进行可视化,可以在屏幕上显示棋盘。
```python
import turtle
# 设置窗口大小
window = turtle.Screen()
window.setup(1200, 1200)
# 定义常量
SIZE = 2000 # 棋盘大小
CELL_SIZE = SIZE // 20 # 格子大小
# 初始化画笔
pen = turtle.Turtle()
pen.speed(0)
pen.hideturtle()
pen.penup()
# 绘制棋盘
for i in range(-SIZE//2, SIZE//2+1, CELL_SIZE):
for j in range(-SIZE//2, SIZE//2+1, CELL_SIZE):
pen.goto(i, j)
pen.pendown()
pen.begin_fill()
for k in range(4):
pen.forward(CELL_SIZE)
pen.right(90)
pen.end_fill()
# 显示结果
turtle.done()
```
这个代码使用了turtle库,首先设置了窗口大小为1200x1200,然后定义了棋盘大小为2000。接着初始化了画笔,并且设置了画笔的速度和隐藏画笔。然后在循环中依次绘制每一个格子,并且填充颜色。最后显示结果。
这个代码可以生成一个2k×2k个方格组成的棋盘,你可以根据需要修改棋盘的大小和格子的大小。