題目鏈接：點(diǎn)擊查看

題目大意：給出 n 個武器及花費(fèi)，m 個防具及花費(fèi)，以及 k 個怪物及屬性，每個怪物的屬性同樣有著攻擊力，防御力以及價值，初始時可以選擇一個武器以及一個防具，如果此時的攻擊力大于怪物的攻擊力，且防御力大于怪物的防御力，則可以打敗這個怪物，并且獲得其掉落的價值，現(xiàn)在問如何挑選初始時的武器可以使得收益最大化

題目分析：二維偏序的好題，補(bǔ)題的時候看到標(biāo)簽上寫著數(shù)據(jù)結(jié)構(gòu)，雙指針和排序，以及這個題目攻擊力和防御力的攻擊范圍都才1e6而不是1e9，加上對于每個怪物是否擊敗都有著兩個維度的限制，所以不難想到要用二維偏序來解決，先對攻擊力排序，這樣就能忽略掉攻擊力帶來的限制了，因為題目的數(shù)據(jù)范圍都在1e6以內(nèi)，所以我們在讀入時將其映射到數(shù)軸上，而不是開一個二維數(shù)組保存，這樣就相當(dāng)于對攻擊力進(jìn)行桶排序了，可以優(yōu)化掉快速排序 logn 的時間復(fù)雜度，最后每個怪物的屬性還是需要開一個三個變量的結(jié)構(gòu)體保存，想一下如何將防御力映射到線段樹上去，因為擊敗某個怪物的條件是攻擊力以及防御力都必須嚴(yán)格大于該怪物，而對攻擊力排序已經(jīng)可以忽略掉攻擊力帶來的影響了，剩下的我們可以將線段樹的每個端點(diǎn)視為防御力的具體數(shù)值，而每個端點(diǎn)所保存的數(shù)值是利潤，若要查詢最終答案，只需要查詢一下每次線段樹中的最大值，再減去當(dāng)前遍歷到的武器的花費(fèi)就是答案了，至于更新線段樹也是比較好想的，因為對于某個怪物的防御力而言，只有大于其防御力的防具才能夠打敗這個怪物，那么只需要對區(qū)間[ x + 1 , n ]都加上這個怪物的價值就好了，其中 x 為這個怪物的防御力，線段樹初始化為每點(diǎn)防御力的價格，因為在將防御力映射到數(shù)軸上之后，會有很多地方的花費(fèi)是 0 ，但并不代表此時的花費(fèi)為 0 ，所以需要預(yù)處理一下，如果某個點(diǎn)的花費(fèi)為 0 ，那么這個點(diǎn)可能會被比這個點(diǎn)大的防具所包含，所以倒著維護(hù)一下就好了，還有一個小細(xì)節(jié)就是可能防御力較高的防具花費(fèi)會比較低，就像樣例給出的數(shù)據(jù)一樣，這個時候還需要維護(hù)一下最小值

還有一些小細(xì)節(jié)就是，因為題目的數(shù)據(jù)剛好卡到int，所以數(shù)據(jù)范圍不會爆int，不過在設(shè)置無窮小的時候，因為極限情況會到達(dá)-2e9，所以要把無窮小設(shè)的小一些

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;const int M=1e6+100;struct node {int x,y,val;bool operator<(const node& a)const{return x<a.x;} }c[N];int a[M],b[M];struct Node {int l,r,mmax,lazy; }tree[M<<2];void pushup(int k) {tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax); }void pushdown(int k) {if(tree[k].lazy){int lz=tree[k].lazy;tree[k].lazy=0;tree[k<<1].lazy+=lz;tree[k<<1|1].lazy+=lz;tree[k<<1].mmax+=lz;tree[k<<1|1].mmax+=lz;} }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].lazy=0;if(l==r){tree[k].mmax=-b[l];return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); }void update(int k,int l,int r,int val) {if(tree[k].r<l||tree[k].l>r)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].mmax+=val;tree[k].lazy+=val;return;}pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k); }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++){int pos,val;scanf("%d%d",&pos,&val);if(a[pos])a[pos]=min(a[pos],val);elsea[pos]=val;}for(int i=1;i<=m;i++){int pos,val;scanf("%d%d",&pos,&val);if(b[pos])b[pos]=min(b[pos],val);elseb[pos]=val;}for(int i=M-2;i>=1;i--){if(!b[i])//如果當(dāng)前位置為0，那么直接用最近的，大于當(dāng)前位置裝備的價格 b[i]=b[i+1];else if(b[i+1])//否則保留最小值 b[i]=min(b[i],b[i+1]);}int limit;for(int i=1;i<M;i++)//找到防御力的最后一個有效位置if(b[i])limit=i;for(int i=1;i<=k;i++)scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].val);sort(c+1,c+1+k);build(1,1,limit);int ans=INT_MIN;int pos=1;for(int i=1;i<M;i++)//遍歷攻擊力(已排序)if(a[i]){while(pos<=k&&c[pos].x<i){if(c[pos].y+1<=limit)//更新防御力update(1,c[pos].y+1,limit,c[pos].val);pos++;}ans=max(ans,tree[1].mmax-a[i]);}printf("%d\n",ans);}

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1321E World of Darkraft: Battle for Azathoth(二维偏序+线段树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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