本文主要是介绍hdu 1156，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
主题思路树状数组：
对线段按x坐标进行排序，从小到大依次遍历，最初开始时把所有点都加入到r边的树状数组中。随着遍历，删去已经遍历过的x坐标的点，并把这些点加入到左边的树状数组中。
需要对树状数组进行统计，以及进行更改。这也是为什么用树状数组。
参考博客：http://www.cnblogs.com/Stomach-ache/p/3871751.html
AC 代码
#include <iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;const int maxn=200005;int l[maxn],r[maxn];struct Line{int x;int y;};bool cmp(Line a,Line b){return a.x<b.x;
}Line line[maxn];
int y[maxn];int n,w;
//BIT (Binary Indexed Tree)int lowbit(int x){return x&(-x);
}void update(int c[],int i,int x){while(i<=w){c[i]+=x;i+=lowbit(i);}
}
int sum(int c[],int i){int ans=0;while(i!=0){ans+=c[i];i-=lowbit(i);}return ans;
}int main()
{while(scanf("%d",&n)&&n!=0){for(int i=0;i<n;i++){scanf("%d%d",&line[i].x,&line[i].y);y[i]=line[i].y;}//sort(y,y+n);//the number unique setw=unique(y,y+n)-y;memset(l,0,sizeof(l));memset(r,0,sizeof(r));// add all point in r at first//sort line by x-ray// sort(line,line+n,cmp);sort(line,line+n,cmp);for(int i=0;i<n;i++){update(r,lower_bound(y,y+w,line[i].y)+1-y,1);}int Stan=-1;int st=0;vector<int> Ollie;for(int i=1;i<=n;i++){if(i==n||line[i].x!=line[i-1].x){// delete element where x=line[i-1].xfor(int j=st;j<i;j++) update(r,lower_bound(y,y+w,line[j].y)+1-y,-1);// search for each yint stan=-1,ollie=-1;for(int j=st;j<i;j++){int f=lower_bound(y,y+w,line[j].y)+1-y;int s=sum(l,f-1)+sum(r,w)-sum(r,f); // bottem-left + top-rightint o=sum(l,w)-sum(l,f)+sum(r,f-1);if(o>ollie){stan=s;ollie=o;}else if(o==ollie){stan=stan<s?stan:s;}}//update Stanif(stan>Stan){Stan=stan;Ollie.clear();Ollie.push_back(ollie);}else if(stan==Stan){Ollie.push_back(ollie);}// add left of i to lfor(int j=st;j<i;j++){update(l,lower_bound(y,y+w,line[j].y)+1-y,1);}st=i;}}//sort(Ollie.begin(),Ollie.end());int len=unique(Ollie.begin(),Ollie.end())-Ollie.begin();printf("Stan: %d; Ollie:",Stan);for(int i=0;i<len;i++)printf(" %d",Ollie[i]);printf(";\n");}return 0;
}
这篇关于hdu 1156的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
