[BZOJ2850/Luogu4475]巧克力王国(KDT)

发布于 2018-05-15  179 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2850/Luogu4475]巧克力王国(KDT)

Description

巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎,因为大家都不喜欢过于甜的巧克力。对于每一块巧克力,我们设x和y为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的评判标准,所以每个人都有两个参数a和b,分别为他自己为牛奶和可可定义的权重,因此牛奶和可可含量分别为x和y的巧克力对于他的甜味程度即为ax + by。而每个人又有一个甜味限度c,所有甜味程度大于等于c的巧克力他都无法接受。每块巧克力都有一个美味值h。现在我们想知道对于每个人,他所能接受的巧克力的美味值之和为多少

Tag

KDT

解决思路

维护二维平面上的若干个点,每次查询这些点中符合要求的。用KDT优化暴力寻找。
需要注意的是,由于坐标和甜味程度都有可能是负数,所以要四个方向都判断一遍。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2850/Luogu4475]巧克力王国(KDT)


HNCJ OIer