TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2018
  • 题目
  • P2018【G2015 第一学期期末赛】何老板卖卡车
    限制 : 时间限制 : 15000 MS   空间限制 : 128000 KB
    问题描述

    何老板开了一家重型卡车店,店中出售n种重型卡车(每种卡车的数量无限),每种卡车都有一定的最大载重量和最大行驶速度。
      到店的客人要求购买一辆载重能力为t吨且速度为s的卡车,客人会首先选择载重能力>=t且与t最接近的车,如果有多款可选,客人会选择速度>=s且与s最接近的那款。
      今天总共来了m个顾客,每个顾客都最多买走了一辆车(有可能没有满足顾客要求的车),请打印出每个顾客购买车辆的情况。

    输入格式

    第一行,一个整数n,表示有n种车
    第二行,n个空格间隔的整数,表示1到n每种车的载重能力
    第三行,n个空格间隔的整数,表示1到n每种车的速度
    第四行,一个整数m,表示有m个顾客
    接下来m行,每行两个整数,表示顾客对载重和速度的要求

    输出格式

    M行,每行两个空格间隔的整数,表示顾客买车的情况,第一个整数表示所购买车辆的载重,第二个整数表示车辆的速度。如果没有买到车,就输出两个空格间隔的0。

    样例输入

    7
    67  88  91  88  99  88  67
    80  92  69  70  85  77  85
    4
    88 76
    88 100
    80 68
    65 90

    样例输出

    88 77
    0 0
    88 70
    0 0

    提示

    数据范围:
    1<=n<=500000
    1<=M<=200000
    0<=车的载重能力<=1000000000
    0<=车的最大速度<=1000000000
    样例说明:
    对于客户提出的条件65 90
    客户首先考虑载重,于是选择载重为67这种车,该车的载重是>=65且与65最接近的一个。
    接着讨论速度,客户要求的速度是>=90,而载重为67的车中,最大速度是85,不满足要求,于是客户放弃购买。