P1752 点菜

    • 31通过
    • 314提交
  • 题目提供者 litc
  • 评测方式 云端评测
  • 标签 二分答案 二叉堆 贪心 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    有n个人到一家餐馆点菜。这家餐馆总共有m道菜,每一道菜都有两个属性——美味度和价格。这n个人每周都会来一次,每次只会点一道菜或不点。在这n个人中,有p个人比较挑剔,他们只能接受美味度大于等于一定值的菜;有q个人比较贫穷,他们只能点价格小于等于一定值的菜。现在请你计算:这些人至少要来几周,才可能能把餐馆的所有的菜都点过一遍?

    输入输出格式

    输入格式:

    第1行,四个正整数n,m,p,q

    第2~m+1行,每行两个数,表示菜的美味度和价格。

    第m+2行p个数,表示p个挑剔的人分别能接受的菜的美味度的下限。

    第m+3行q个数,表示q个贫穷的人分别能点的菜的价格的上限。

    输出格式:

    一行一个数,即这些人最少要来的周数。若不论这些人来几周都不可能把菜点过一遍,输出-1。

    输入输出样例

    输入样例#1: 复制
    2 3 1 1
    5 2
    5 3
    6 4
    5
    1
    输出样例#1: 复制
    3
    

    说明

    对于20%的数据,m<=20

    对于40%的数据,m<=2000

    对于100%的数据,p+q<=n<=50000,m<=200000

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