题干:
蒜头去嘉年华玩儿套圈圈,是这么玩儿的。有一些瓶口口径不同的啤酒瓶,瓶子里面有一些奖品。如果蒜头用手上的圈圈套中了啤酒瓶,那么奖品就归他了。
假设蒜头君无限精准,指哪儿打哪儿,并且蒜头了解到,只有圈圈的半径 严格大于 啤酒瓶半径,才能套中。
并且蒜头君知道自己手上的每个圈圈的半径,也知道每个啤酒瓶的半径和里面物品相对应的价值。
当然,奖品是无限多的,意思就是如果蒜头君套中了一个啤酒瓶并且获得了奖品,下次可以继续套获得同样的奖品。
现在蒜头君想问你,他最大能获得多少价值。
输入格式第一行两个整数 NN,MM 代表圈圈的个数和啤酒瓶的个数。
第二行 NN 个整数代表圈圈的半径 r_crc。
接下来 MM 行每行两个整数 r_brb,vv 代表啤酒瓶的半径 rr 和相应的价值 vv。
输出格式输出一个整数,代表蒜头能获得的最大价值。
数据范围对于 30\%30% 的数据:N = 1N=1 , M = 1M=1 , 1 \le r_c , r_b , v \le 1001≤rc,rb,v≤100 。
对于 60\%60% 的数据:1 \le N \times M \le 10000001≤N×M≤1000000, 1 \le r_c , r_b , v \le 1001≤rc,rb,v≤100 , 保证所有的价值 vv 都相等。
对于 100\%100% 的数据:1 \le N \times M \le 10000001≤N×M≤1000000, 1 \le r_c , r_b , v \le 1001≤rc,rb,v≤100。
输出时每行末尾的多余空格,不影响答案正确性
样例输入复制
2 22 31 22 3样例输出复制
5解题报告:
但是不知道为啥,这个AC代码1竟让比代码2要慢。。。这个AC代码1几乎是线性的啊。(应该说明有极端数据n=1e6,m=1这样的,就把nlogn给卡了)
AC代码1:(复杂度O(nlogn+mlogm+n+m),109ms)
#include#include#include#include#include#include#include#include#include#include#define ll long long#define pb push_back#define pm make_pair#define fi first#define se secondusing namespace std;const int MAX = 2e6 + 5;typedef pair PLL;ll R[MAX],r[MAX],v[MAX];PLL p[MAX];int main(){int n,m;cin>>n>>m;for(int i = 1; i>m;for(int i = 1; i