題干：

蒜頭去嘉年華玩兒套圈圈，是這么玩兒的。有一些瓶口口徑不同的啤酒瓶，瓶子里面有一些獎(jiǎng)品。如果蒜頭用手上的圈圈套中了啤酒瓶，那么獎(jiǎng)品就歸他了。

假設(shè)蒜頭君無限精準(zhǔn)，指哪兒打哪兒，并且蒜頭了解到，只有圈圈的半徑 嚴(yán)格大于 啤酒瓶半徑，才能套中。

并且蒜頭君知道自己手上的每個(gè)圈圈的半徑，也知道每個(gè)啤酒瓶的半徑和里面物品相對(duì)應(yīng)的價(jià)值。

當(dāng)然，獎(jiǎng)品是無限多的，意思就是如果蒜頭君套中了一個(gè)啤酒瓶并且獲得了獎(jiǎng)品，下次可以繼續(xù)套獲得同樣的獎(jiǎng)品。

現(xiàn)在蒜頭君想問你，他最大能獲得多少價(jià)值。

輸入格式

第一行兩個(gè)整數(shù)?NN，MM?代表圈圈的個(gè)數(shù)和啤酒瓶的個(gè)數(shù)。

第二行?NN?個(gè)整數(shù)代表圈圈的半徑?r_crc?。

接下來?MM?行每行兩個(gè)整數(shù)?r_brb?，vv?代表啤酒瓶的半徑?rr?和相應(yīng)的價(jià)值?vv。

輸出格式

輸出一個(gè)整數(shù)，代表蒜頭能獲得的最大價(jià)值。

數(shù)據(jù)范圍

對(duì)于?30\%30%?的數(shù)據(jù)：N = 1N=1?,?M = 1M=1?,?1 \le r_c , r_b , v \le 1001≤rc?,rb?,v≤100?。

對(duì)于?60\%60%?的數(shù)據(jù)：1 \le N \times M \le 10000001≤N×M≤1000000,?1 \le r_c , r_b , v \le 1001≤rc?,rb?,v≤100?, 保證所有的價(jià)值?vv?都相等。

對(duì)于?100\%100%?的數(shù)據(jù)：1 \le N \times M \le 10000001≤N×M≤1000000,?1 \le r_c , r_b , v \le 1001≤rc?,rb?,v≤100。

輸出時(shí)每行末尾的多余空格，不影響答案正確性

樣例輸入復(fù)制

2 2 2 3 1 2 2 3

樣例輸出復(fù)制

5

解題報(bào)告：

? ?但是不知道為啥，這個(gè)AC代碼1竟讓比代碼2要慢。。。這個(gè)AC代碼1幾乎是線性的啊。（應(yīng)該說明有極端數(shù)據(jù)n=1e6,m=1這樣的，就把nlogn給卡了）

AC代碼1：（復(fù)雜度O(nlogn+mlogm+n+m)，109ms）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e6 + 5; typedef pair<ll,ll > PLL; ll R[MAX],r[MAX],v[MAX]; PLL p[MAX]; int main() {int n,m;cin>>n>>m;for(int i = 1; i<=n; i++) scanf("%lld",R+i);for(int i = 1; i<=m; i++) scanf("%lld%lld",&p[i].first,&p[i].second);sort(R+1,R+n+1);sort(p+1,p+m+1);ll ans = 0,maxx = 0,j=1;for(int i = 1; i<=n; i++) {while(R[i] > p[j].first && j<=m) maxx = max(maxx,p[j].second),j++;ans += maxx;} printf("%lld\n",ans);return 0 ;}

AC代碼2：（復(fù)雜度O(n*m)，66ms）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e6 + 5; ll R[MAX],r[MAX],v[MAX]; int main() {int n,m;cin>>n>>m;for(int i = 1; i<=n; i++) scanf("%lld",R+i);for(int i = 1; i<=m; i++) scanf("%lld%lld",r+i,v+i);ll ans = 0,maxx = 0;for(int i = 1; i<=n; i++) {maxx = 0;for(int j = 1; j<=m; j++) {if(R[i] > r[j]) maxx = max(maxx,v[j]);}ans += maxx;} printf("%lld\n",ans);return 0 ;}

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【计蒜客信息学模拟赛1月月赛 - B】蒜头套圈圈（贪心，前缀最大值）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。