P3324 [SDOI2015]星际战争

    • 263通过
    • 1.1K提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 二分答案 最大流 网络流 2015 山东 Special Judge
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    3333年,在银河系的某星球上,X军团和Y军团正在激烈地作战。

    在战斗的某一阶段,Y军团一共派遣了N个巨型机器人进攻X军团的阵地,其中第i个巨型机器人的装甲值为Ai。当一个巨型机器人的装甲值减少到0或者以下时,这个巨型机器人就被摧毁了。

    X军团有M个激光武器,其中第i个激光武器每秒可以削减一个巨型机器人Bi的装甲值。激光武器的攻击是连续的。

    这种激光武器非常奇怪,一个激光武器只能攻击一些特定的敌人。Y军团看到自己的巨型机器人被X军团一个一个消灭,他们急需下达更多的指令。

    为了这个目标,Y军团需要知道X军团最少需要用多长时间才能将Y军团的所有巨型机器人摧毁。但是他们不会计算这个问题,因此向你求助。

    输入输出格式

    输入格式:

    第一行,两个整数,N、M。第二行,N个整数,A1、A2...AN。第三行,M个整数,B1、B2...BM。接下来的M行,每行N个整数,这些整数均为0或者1。这部分中的第i行的第j个整数为0表示第i个激光武器不可以攻击第j个巨型机器人,为1表示第i个激光武器可以攻击第j个巨型机器人。

    输出格式:

    一行,一个实数,表示X军团要摧毁Y军团的所有巨型机器人最少需要的时间。输出结果与标准答案的绝对误差不超过10-3即视为正确。

    输入输出样例

    输入样例#1: 复制
    2 2
    3 10
    4 6
    0 1
    1 1
    输出样例#1: 复制
    1.300000

    说明

    【样例说明1】

    战斗开始后的前0.5秒,激光武器1攻击2号巨型机器人,激光武器2攻击1号巨型机器人。1号巨型机器人被完全摧毁,2号巨型机器人还剩余8的装甲值;

    接下来的0.8秒,激光武器1、2同时攻击2号巨型机器人。2号巨型机器人被完全摧毁。

    对于全部的数据,1<=N, M<=50,1<=Ai<= $10^5$ ,1<=Bi<=1000,输入数据保证X军团一定能摧毁Y军团的所有巨型机器人

    [spj]

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。