Fair Photography [Brian Dean, 2014]
http://218.5.5.242:9018/JudgeOnline/problem.php?id=1592
题目描述
Farmer John’s N cows (1 <= N <= 100,000) are standing at various positions along
a long one-dimensional fence. The ith cow is standing at position x_i (an
integer in the range 0…1,000,000,000) and has breed b_i (either ‘G’ for
Guernsey or ‘H’ for Holstein). No two cows occupy the same position.
FJ wants to take a photo of a contiguous interval of cows for the county
fair, but we wants all of his breeds to be fairly represented in the photo.
Therefore, he wants to ensure that, for whatever breeds are present in the
photo, there is an equal number of each breed (for example, a photo with
all Holsteins is ok, a photo with 27 Holsteins and 27 Guernseys is ok, but a
photo with 10 Holsteins and 9 Guernseys is not ok). Help FJ take his fair
photo by finding the maximum size of a photo that satisfies FJ’s
constraints. The size of a photo is the difference between the maximum and
minimum positions of the cows in the photo. It is possible that FJ could
end up taking a photo of just a single cow, in which case this photo would
have size zero.
PROBLEM NAME: fairphoto
输入
* Line 1: The integer N.
* Lines 2..1+N: Line i+1 contains x_i and b_i.
输出
* Line 1: A single integer indicating the maximum size of a fair photo.
样例输入
|
1 2 3 4 5 6 7 |
<span class="sampledata">6 4 G 10 H 7 G 16 G 1 G 3 H</span> |
样例输出
|
1 |
<span class="sampledata">7</span> |
提示
INPUT DETAILS:
There are six cows with breeds (from left to right) G, H, G, G, H, G.
OUTPUT DETAILS:
The largest fair photo Farmer John can take is of the middle 4 cows,containing 2 Holsteins and 2 Guernseys.
题解
两种牛数量相等用1，-1累加和。。。
再考虑全都是一种牛的情况
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline int read() { 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=x*10+ch-'0';ch=getchar();} return x*f; } int n,ans; int fir[200005]; struct data{ int pos,val; }a[100005]; bool operator<(data a,data b) { return a.pos<b.pos; } int main() { n=read(); char ch[5]; for(int i=1;i<=n;i++) { a[i].pos=read(); scanf("%s",ch+1); if(ch[1]=='G')a[i].val=-1; else a[i].val=1; } sort(a+1,a+n+1); int now=100000;fir[now]=a[1].pos; for(int i=1;i<=n;i++) { now+=a[i].val; if(!fir[now])fir[now]=a[i+1].pos; else ans=max(ans,a[i].pos-fir[now]); } int t1,t2; if(a[1].val==1)t1=a[2].pos,t2=a[1].pos; else t1=a[1].pos,t2=a[2].pos; for(int i=2;i<=n;i++) { if(a[i].val==1)t1=a[i+1].pos,ans=max(ans,a[i].pos-t2); else t2=a[i+1].pos,ans=max(ans,a[i].pos-t1); } printf("%d\n",ans); return 0; } |
OI 课件=>
