P4602 [CTSC2018]混合果汁

    • 108通过
    • 220提交
  • 题目提供者 Imagine
  • 评测方式 云端评测
  • 标签 WC/CTSC/集训队 2018 O2优化 新云端
  • 难度 省选/NOI-
  • 时空限制 2000ms / 512MB

题解

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

    推荐的相关题目 显示

    题目描述

    小 R 热衷于做黑暗料理,尤其是混合果汁。

    商店里有 $n$ 种果汁,编号为 $0,1,\cdots,n-1$ 。$i$ 号果汁的美味度是 $d_i$,每升价格为 $p_i$。小 R 在制作混合果汁时,还有一些特殊的规定,即在一瓶混合果汁中,$i$ 号果汁最多只能添加 $l_i$ 升。

    现在有 $m$ 个小朋友过来找小 R 要混合果汁喝,他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中,第 $j$ 个小朋友希望他得到的混合果汁总价格不大于 $g_j$,体积不小于 $L_j$。在上述这些限制条件下,小朋友们还希望混合果汁的美味度尽可能地高,一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。

    输入输出格式

    输入格式:

    输入第一行包含两个正整数 $n, m$,表示果汁的种数和小朋友的数量。接下来 $n$ 行,每行三个正整数 $d_i, p_i, l_i$,表示 $i$ 号果汁的美味度为 $d_i$,每升价格为$p_i$,在一瓶果汁中的添加上限为 $l_i$。

    接下来 $m$ 行依次描述所有小朋友:每行两个数正整数 $g_j, L_j$ 描述一个小朋友,表示他最多能支付 $g_j$ 元钱,他想要至少 $L_j$ 升果汁。

    输出格式:

    对于所有小朋友依次输出:对于每个小朋友,输出一行,包含一个整数,表示他能喝到的最美味的混合果汁的美味度。如果无法满足他的需求,则输出 $-1$。

    输入输出样例

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

    说明

    对于所有的测试数据,保证 $n, m \le 100000$,$1 \le d_i,p_i,l_i \le 10^5, 1 \le g_j, L_j \le 10^{18}$。

    测试点编号 $n=$ $m=$ 其他限制
    1,2,3 $10$ $10$
    4,5,6 $500$ $500$
    7,8,9 $5000$ $5000$
    10,11,12 $100000$ $100000$ $p_i=1$
    13,14,15 $100000$ $100000$ $l_i=1$
    16,17,18,19,20 $100000$ $100000$
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。