最大值树状数组)"/>
C. Fountains(最大值树状数组)
有 n 个泉水,c 枚金币,d 枚钻石,每个泉水可以带来 b 点欢乐值,但要消耗 p 枚金币或钻石,只能买两座泉水,问最大的快乐值
这个题明显贪心啊如果两种泉水各买一座还好,但是有可能一种泉水买两坐,剩下的一种不买,所以利用树状数组求区间最大值
const int N=2e5+5;int n,m,t;int i,j,k;int c[N],d[N];int get_max(int x,int *aim)//1~x 的最大值
{int ans=0;while(x){ans=max(ans,aim[x]);x-=lowbit(x);}return ans;
}
void update(int x,int val,int *aim)
{while(x<=N){aim[x]=max(aim[x],val);x+=lowbit(x);}
}
int main()
{IOS;for(int C,D;cin>>n>>C>>D;){int ans=0,maxx;for(i=1;i<=n;i++){int b,p; char ch;cin>>b>>p>>ch;maxx=0;if(ch=='C'){maxx=get_max(D,d);//用 D 能买到的最大值if(p>C) continue;maxx=max(maxx,get_max(C-p,c));//将当前的这个买下,用剩下的钱再买一个 cupdate(p,b,c);}else{maxx=get_max(C,c);if(p>D) continue;maxx=max(maxx,get_max(D-p,d));update(p,b,d);}if(maxx)ans=max(maxx+b,ans);}cout<<ans<<endl;}//PAUSE;
}
更多推荐
C. Fountains(最大值树状数组)
发布评论