公平摄影(前缀和)

公平摄影(前缀和)

农夫约翰的 N 头奶牛站在一维长围栏的不同位置。第 i 头牛位于位置 xi，其所属品种为 bi（根西岛牛或荷斯坦牛）。

所有奶牛的位置各不相同。

约翰想给一段连续区间内的奶牛拍摄一张照片，用来在乡村集市上展览。
但是我们希望他所有品种的奶牛都能在照片中得到公平的展示。因此，他希望确保无论照片中出些哪些品种的奶牛，每种品种的奶牛在照片中的数量都必须相等。

例如，一张照片中只包含荷斯坦牛是可以的，包含荷斯坦牛和根西岛牛各 27 头也没问题，但是包含 10 头荷斯坦牛和 9 头根西岛牛则不可以。

请确定，约翰可以拍下的满足以上条件的照片的最大尺寸。
照片的尺寸是指照片中奶牛最大和最小位置之间的差。
约翰最终可能只拍下一头奶牛，这种情况下，照片尺寸为 0。

输入格式
第一行包含整数 N。

接下来 N 行，每行包含一个整数 xi 和一个字符 bi（H 表示荷斯坦牛，G 表示根西岛牛）。

输出格式
输出照片的最大尺寸。

数据范围
1≤N≤10⁵,0≤xi≤10⁹

输入样例：
6
4 G
10 H
7 G
16 G
1 G
3 H

输出样例：
7

样例解释
共 6 头牛，从左到右排列顺序为 G,H,G,G,H,G。

最佳摄影方案是拍中间四头奶牛，恰好荷斯坦牛和根西岛牛各两头。

思路： 首先明确题意，可以只拍一种牛，也可以拍两种，那我们就要分两种情况来求最大尺寸，题所给的距离是无序的，所以我们第一步肯定是要按距离排序的，当照片中出现两种牛，要保证他们的数量相等，那我们就可以令一种为1，另一种为-1，当他们的前缀和为0时，表示区间一定是两种牛数量相等的，或两个前缀和l,r相等时，区间[l+1,r]（不懂就举例计算 ）中两种牛的数量也是相等的，想要区间最大，就记录0，-1，1第一次出现的位置，此时的l是最小的，然后枚举计算答案即可

AC代码：

#include<stdio.h>
#include<string.h>
#include<map>
#define ll long long
#include<algorithm>
using namespace std;
const int N=1e5+10;
map<int,int>book;
struct pp
{
	int x;
	int y;
}p[N];
bool cmp(pp a,pp b)
{
	return a.x<b.x; 
}
int main()
{
	int n,a,b,i,j;
	char k[3];
	scanf("%d",&n);
	for(i=1;i<=n;i++)//题所给x下标从0开始，为防止下面计算错误，这里下标从1开始
	{
		scanf("%d %s",&p[i].x,k);
		if(k[0]=='G')//赋值
		p[i].y=1;
		else
		p[i].y=-1;
	}
	sort(p+1,p+n+1,cmp);
//	memset(book,-1,sizeof(book));
	book[0]=p[1].x;//当有  2  3 G 10 H，这种样例时，不赋值book[0]答案是错误的
	int sum=0,maxx=0,pre=-2,ipre;
	for(i=1;i<=n;i++)
	{
		if(p[i].y==pre) maxx=max(maxx,p[i].x-ipre);//只有一种牛
		else pre=p[i].y,ipre=p[i].x;
		sum+=p[i].y;//两种都有
		if(!book[sum])//因为sum可能为负，所以这里用了map来存，也可以用数组+偏移量
		book[sum]=p[i+1].x;//这里直接记录l+1
		else
		maxx=max(maxx,p[i].x-book[sum]);
	//	printf("%d   %d  %d++n",sum,book[sum],maxx);
	}
	printf("%dn",maxx);
	return 0;
}

最后

以上就是复杂店员为你收集整理的公平摄影(前缀和)的全部内容，希望文章能够帮你解决公平摄影(前缀和)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。