东方吧 关注:646,594贴子:17,563,270
  • 13回复贴,共1

学校OJ上的题,帮我看看。

只看楼主收藏回复

题目描述
射命丸文是鸦天狗, 在幻想乡出现之初就存在了, 拥有操纵风的能力, 是幻想
乡中最快的存在, 从事记者的工作。
这一天, 在幻想乡发生了N起大新闻, 第i起大新闻发生在坐标(Xi,Yi)处。 射命
丸文从坐标(0,0)处出发, 按照新闻发生的时间顺序前往各个新闻发生地收集资料, 最
后回到坐标(0,0)处。 虽然她的速度很快, 但是她只会横冲直撞, 换句话说, 她的移动
必须平行于某条坐标轴。 而且她的力量是有限的, 她移动的总距离不能超过D。 所以她
不得不放弃一些大新闻的资料收集。 请问她最多可以收集多少起大新闻的资料?
输入
第一行一个非负整数N, 表示大新闻的数量。
接下来N行, 每行两个整数Xi和Yi, 表示第i起大新闻发生地的坐标。 按照大新
闻发生的时间顺序给出各个坐标。
接下来一行一个非负整数D, 表示她移动的总距离的限制。
输出
输出一个整数, 表示她最多能收集多少起大新闻的资料。


IP属地:四川1楼2020-10-07 21:23回复
    感觉是动归,给个数据范围


    2楼2020-10-07 21:25
    收起回复
      这不是很简单吗?一个循环加一个判断就可以了。a=0表示收集的新闻数量,循环N次,每次判断|xi|+|yi|是否大于D/2,大于,则跳过,不大于则a++


      IP属地:广东来自Android客户端6楼2020-10-07 23:06
      收起回复
        既然是按时间顺序来的就直接循环吧,我还以为是什么神仙贪心题。
        (不过为什么会在东方吧看到这种东西)


        IP属地:湖南8楼2020-10-08 12:35
        回复
          BFS怎么样


          IP属地:上海9楼2020-10-08 12:39
          回复
            数据范围?


            IP属地:上海来自Android客户端10楼2020-10-09 02:15
            回复