本文主要是介绍poj2464Brownie Points II(树状数组)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
晚上写了好久，终于把奇丑无比的代码改好了，试了几个样例都没问题，然后1A，真舒服
题目大意就是坐标平面上给N个点，然后先是Stan经过一个点做一条竖线，随之Ollie在Stan所做竖线上所有的点中选一个点做一条横线，两条线将平面分为四块，
Stan的得分是右上和左下两块中点数之和，Ollie得分是左上和右下两块中点数之和，在直线上的点统统不计
最关键的是：两个人都想让自己的得分尽量高，然后输出Stan至少能得多少分（是是是Stan是绝顶聪明的一定不会放水选次优解的），且输出Ollie在每一种Stan
取到Stan的最优解时Ollie能拿多少分
首先N只有200000，第一想法就是暴力枚举两条线的交点，这样只要能快速求出对应四个块有多少个点就OK了
这个时候我想着看能不能降一维，因为开不下二维树状数组，降维首先想到将某一关键字排序，但好像都不能成功降维，不过隐约可以感觉到要以x为关键字排序
然后想想维护y轴可以用树状数组，在暴力扫的时候用两个树状数组，一个维护现在还没有扫到的点（那么这些点的x值肯定大于当前点的x值），所以在这个树状
数组里可以查询右上和右下的点，另一个树状数组用于维护扫过的点，那么这些点的x值肯定小于当前点的x值，所以这个树状数组里可以查询左上和左下的点
不过注意x值相同的点之间的处理，而且y是要离散化一下的
代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
const int maxn=200005;
int N;
struct BIT{int t[maxn];void init(){memset(t,0,sizeof t);}void update(int x,int v){while(x<maxn){t[x]+=v;x+=(x&-x);}}long long query(int x){int ans=0;while(x){ans+=t[x];x-=(x&-x);}return ans;}
}thl,thr;
struct node
{int x,y,id;
}num[maxn];
bool cmp(node a,node b)
{return a.x<b.x;
}
bool CMP(node a,node b)
{return a.y<b.y;
}
int st[maxn];
int main()
{while(~scanf("%d",&N)&&N){int res=-1;int tot=0;thl.init(),thr.init();for(int i=0;i<N;i++)scanf("%d%d",&num[i].x,&num[i].y);sort(num,num+N,CMP);num[0].id=1;for(int i=1;i<N;i++)if(num[i].y==num[i-1].y)num[i].id=num[i-1].id;else num[i].id=num[i-1].id+1;for(int i=0;i<N;i++)thr.update(num[i].id,1);sort(num,num+N,cmp);int i=0;while(i<N){int tempanss=10000000;int temp=i;while(num[temp].x==num[temp+1].x){temp++;thr.update(num[temp].id,-1);}for(int j=i;j<=temp;j++){int ans=thl.query(num[j].id-1)+thr.query(200001)-thr.query(num[j].id);tempanss=min(ans,tempanss);}if(temp>i)thr.update(num[i].id,-1);int ti=i;while(ti<=temp){if(tempanss>maxn){int ans=thl.query(num[ti].id-1)+thr.query(200001)-thr.query(num[ti].id);tempanss=min(tempanss,ans);}if(tempanss>res&&tempanss<maxn){tot=0;int ans=thl.query(200005)-thl.query(num[ti].id)+thr.query(num[ti].id-1);st[tot++]=ans;res=tempanss;}else if(tempanss==res&&tempanss<maxn){int ans=thl.query(200005)-thl.query(num[ti].id)+thr.query(num[ti].id-1);st[tot++]=ans;}ti++;}if(temp==i)thr.update(num[i].id,-1);while(i<=temp){thl.update(num[i].id,1);i++;}}sort(st,st+tot);int a=unique(st,st+tot)-st;printf("Stan: %d; Ollie:",res);for(int i=0;i<a;i++)printf(" %d",st[i]);printf(";\n");}return 0;
}这篇关于poj2464Brownie Points II(树状数组)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
