FJ的N(1 <= N <= 100,000)头牛站在一个数轴的不同点上。第I头牛站在xi位置(0...1,000,000,000),并有一个品种标志BI(G或H)。没有两头牛站在同一位置。
FJ想给他的牛们拍照。他希望照片中牛的品种数量是均衡的。例如,一个照片中全是H牛是可以的,一个照片中有27个G牛和27H牛也是可以的,但一个照片10个G牛和9个H牛不可以)。帮助FJ计算出让他满意的照片中最远位置的两头牛的距离。有可能在FJ的照片中只有一头牛,这时计算的距离为0.
PROBLEM NAME: fairphoto
INPUT FORMAT:
* Line 1: The integer N.
* Lines 2..1+N: Line i+1 contains x_i and b_i.
SAMPLE INPUT (file fairphoto.in):
6
4 G
10 H
7 G
16 G
1 G
3 H
INPUT DETAILS: There are six cows with breeds (from left to right) G, H, G, G, H, G.
OUTPUT FORMAT:
Line 1: A single integer indicating the maximum size of a fair photo.
SAMPLE OUTPUT (file fairphoto.out):
7
OUTPUT DETAILS: The largest fair photo Farmer John can take is of the middle 4 cows, containing 2 Holsteins and 2 Guernseys.
我第一次做的代码:
前缀和简单记录区间两种奶牛个数
数组不够大且超时,只得了30分
前缀和记录:
for(int i=1;i<=n;i++)
{
f[i][i]=0;
if(a[i].ch=='H') sumh[i]++;
if(a[i].ch=='G') sumg[i]++;
}
for(int i=1;i<=n;i++)
{
sumh[i]+=sumh[i-1];
sumg[i]+=sumg[i-1];
}
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #include<vector> #include<map> #include<set> #include<queue> #include<string> #define inf 1000000000 #define maxn 300000 #define maxm 500+100 #define eps 1e-10 #define ll long long #define pa pair<int,int> #define for0(i,n) for(int i=0;i<=(n);i++) #define for1(i,n) for(int i=1;i<=(n);i++) #define for2(i,x,y) for(int i=(x);i<=(y);i++) #define for3(i,x,y) for(int i=(x);i>=(y);i--) #define mod 1000000007 using namespace std; /*************** date:10-30 time:5:00-5:34 baoli note: ***************/ inline ll int read() { ll int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') {x=10*x+ch-'0';ch=getchar();} return x*f; } //const int M=1e5+10; const int M=7000; struct moo{int pos;char ch;}a[M]; int n,f[M][M],sumh[M],sumg[M],pos[M],ans=0;//too large? bool cmp(moo x,moo y) { return x.pos<y.pos; } int main() { // freopen("fairphoto.in","r",stdin); // freopen("fairphoto.out","w",stdout); n=read(); memset(f,255,sizeof(f)); memset(sumh,0,sizeof(sumh)),memset(sumg,0,sizeof(sumg)); for(int i=1;i<=n;i++) {a[i].pos=read();a[i].ch=getchar();} sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { f[i][i]=0; if(a[i].ch=='H') sumh[i]++; if(a[i].ch=='G') sumg[i]++; } for(int i=1;i<=n;i++) { sumh[i]+=sumh[i-1]; sumg[i]+=sumg[i-1]; } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { int tmp1=sumh[j]-sumh[i-1], tmp2=sumg[j]-sumg[i-1]; if(tmp1==0||tmp2==0||tmp1==tmp2) { f[i][j]=max(f[i][j],a[j].pos-a[i].pos); } ans=max(ans,f[i][j]); } printf("%d\n",ans); return 0; }
正解:
1、将两种奶牛分别看做-1和1。
原问题转化为:已知一个类似0/1(-1与1)串,求满足下列任一条件的最大区间:该区间内全部为-1,全部为1或者1与-1数量相等。
前缀和为0则表明该区间两种牛数量相同。常见处理角度,使问题简化许多。
2、O(n)算法:
定义数组last[x]记录满足sum[pos]==x的最小pos
注意:数组下标不为负。将所有x统一加上n
遍历所有前缀和,找到与当前奶牛i前缀和相等且距离最远的奶牛位置j
则[j+1,i]区间为满足第三种情况的区间。
对于前两种情况,一同用num[]记录判断即可