CodeForces - 799C Fountains
题意：一个人要建造两个喷泉，有两种货币，每个喷泉的花费只能使用一种货币，每个喷泉都有一定的美丽值，给
出喷泉的个数及两种货币的总量，每个喷泉的美丽值和花费，输出建造两个喷泉时能达到的最大美丽值，如果不能建
造两个喷泉，输出0
思路：总共分三种情况：用C货币建造一个用D货币建造一个，用C货币建造两个，用D货币建造两个，第一种情况
简单，分别求出用每种货币能够建造的最大美丽值的喷泉，在加起来即可。后两种情况是一样的，枚举每一个喷泉，
如果枚举的这一个喷泉的花费为a，建造另一个喷泉的花费在区间[1，total -a]里，在这个区间里找出最大的美丽值，区
间最值问题用到了线段树，但这里是边枚举边更新，为了避免建造两个相同的喷泉
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+100;
struct foun{
int beauty;
int cost;
}C[MAXN],D[MAXN];
struct NODE{
int l;
int r;
int max;
}segTree[MAXN*4];
void pushup(int num)
{
segTree[num].max=max(segTree[num<<1].max,segTree[num<<1|1].max);
}
void build(int num,int l,int r)
{
segTree[num].l=l;
segTree[num].r=r;
segTree[num].max=0;
if(l==r) return;
int mid=(l+r)>>1;
build(num<<1,l,mid);
build(num<<1|1,mid+1,r);
}
int query(int num,int l,int r)
{
if(segTree[num].l==l&&segTree[num].r==r)
{
return segTree[num].max;
}
int mid=(segTree[num].l+segTree[num].r)>>1;
if(r<=mid) return query(num<<1,l,r);
else if(l>mid) return query(num<<1|1,l,r);
else return max(query(num<<1,l,mid),query(num<<1|1,mid+1,r));
}
void update(int num,int pos,int val)
{
if(segTree[num].l==segTree[num].r)
{
segTree[num].max=max(segTree[num].max,val);
return;
}
int mid=(segTree[num].l+segTree[num].r)>>1;
if(pos<=mid) update(num<<1,pos,val);
else update(num<<1|1,pos,val);
pushup(num);
}
int main(void)
{
int n,c_total,d_total;
cin>>n>>c_total>>d_total;
int c_count=0,d_count=0;
int beauty,cost;
char type[2];
int maxc=0,maxd=0;
int ans=0;
for(int i=0;i<n;i++)
{
cin>>beauty>>cost>>type;
if(type[0]=='C')
{
if(cost<=c_total) //把用C不能购买的喷泉去掉
{
C[c_count].beauty=beauty;
C[c_count++].cost=cost;
maxc=max(beauty,maxc); //找出能用C买的美丽值最大的喷泉
}
}
else
{
if(cost<=d_total) //把用D不能购买的喷泉去掉
{
D[d_count].beauty=beauty;
D[d_count++].cost=cost;
maxd=max(beauty,maxd); //找出能用D买的美丽值最大的喷泉
}
}
}
if(maxc!=0&&maxd!=0) //用C买一个，用D买一个的最大美丽值
ans=maxc+maxd;
//用C买两个喷泉的最大美丽值
build(1,1,100000);
for(int i=0;i<c_count;i++)
{
int res=0;
if(c_total-C[i].cost!=0)
res=query(1,1,c_total-C[i].cost);
if(res!=0)
ans=max(ans,C[i].beauty+res);
update(1,C[i].cost,C[i].beauty);
}
//用D买两个喷泉的最大美丽值
build(1,1,100000);
for(int i=0;i<d_count;i++)
{
int res=0;
if(d_total-D[i].cost!=0)
res=query(1,1,d_total-D[i].cost);
if(res!=0)
ans=max(ans,D[i].beauty+res);
update(1,D[i].cost,D[i].beauty);
}
cout<<ans<<endl;
return 0;
}
