首页 > 代码库 > bzoj1637[Usaco2007 Mar]Balanced Lineup*

bzoj1637[Usaco2007 Mar]Balanced Lineup*

2024-08-14 12:30:25   221人阅读

bzoj1637[Usaco2007 Mar]Balanced Lineup

题意：

n头牛，第i头牛位置为ai，种族为bi（只能为0，1），求一个区间（按数轴位置），使得区间两端牛距离差最大且两种种族牛数相等。n≤50000。

题解：

按位置排序。然后利用前缀和sum[i][0]-sum[j-1][0]=sum[i][1]-sum[j-1][1]，sum[i][0]-sum[i][1]=sum[j-1][0]-sum[j-1][1]，故用个set维护sum[i][0]-sum[i][1]的值，每次找一下set里有没有与当前两个sum元素差相等的值，距离差和答案比较一下。

代码：

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <set> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 50010 7 #define INF 0x3fffffff 8 using namespace std; 9 10 inline int read(){11     char ch=getchar(); int f=1,x=0;12     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}13     while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();14     return f*x;15 }16 struct nd{int id,v; bool operator < (const nd &a)const{return v<a.v;};};17 nd nds[maxn]; set<nd>st; int n,sm[2][maxn],ans;18 int main(){19     n=read(); inc(i,1,n){int x=read(),y=read(); nds[i]=(nd){x,y};} sort(nds+1,nds+1+n);20     inc(i,1,n)sm[0][i]=sm[0][i-1],sm[1][i]=sm[1][i-1],sm[nds[i].id][i]++;21     inc(i,1,n){22         set<nd>::iterator sti=st.find((nd){0,sm[0][i]-sm[1][i]});23         if(sti!=st.end()){ans=max(ans,nds[i].v-nds[sti->id+1].v);}24         else st.insert((nd){i,sm[0][i]-sm[1][i]});25     }26     printf("%d",ans); return 0;27 }

 

20160922

bzoj1637[Usaco2007 Mar]Balanced Lineup*


联系
我们