公平摄影

题目链接：https://www.acwing.com/problem/content/1915/

题解

假设 h 代表+1，g 代表-1，将每头牛按照坐标从小到大排序，那么该问题就转化为了找到一段区间 [l,r] 使该 l 和 r 的前缀和相同，可以用 map 记录第一次出现的最左边的前缀和坐标，当该数再一次出现时可以用 map 求出长度，注意要加一个 map[0]，用来特殊判断 G H 这类情况出现。

该题还说明区间内只有一种牛也是可以的，所以用双指针来找一段区间内全部是同种牛的区间长度。

代码

#include 
#include 
#include 
#include 
#define x first
#define y second
using namespace std;
const int N = 1e5+10;

int n;
int a[N];
map mp;
pair p[N];

int main()
{
    cin >> n;
    for (int i = 1 ; i <= n ; i ++ )
    {
        cin >> p[i].x >> p[i].y;
    }
    
    sort(p + 1,p + 1 + n);
    
    int ans = 0;
    mp[0] = 0;
    for (int i = 1 ; i <= n ; i ++ )
    {
        if(p[i].y == 'H') a[i] = a[i-1] + 1;
        else a[i] = a[i-1] - 1;
        
        if(mp.count(a[i])) 
        {
            ans = max(ans,p[i].x - p[mp[a[i]] + 1].x);
        }
        else mp[a[i]] = i;
    }
    
    for (int i = 1 ; i <= n ; i ++ )
    {
        int j = i + 1;
        char c = p[i].y;
        while(p[j].y == c) j ++ ;
        ans = max(ans,p[j - 1].x - p[i].x);
        i = j - 1;
    }
    cout << ans << endl;
    return 0;
}
AcWing前缀和

相关

前缀和后缀表达式

【题解】AcWing 1387.家的范围

【题解】Acwing 1270 数列区间最大值

AcWing 1208.翻硬币

AcWing 1208.翻硬币

luogu P1463 & AcWing 198 反素数 题解

AcWing 1294. 樱花 题解

【前缀和】最大子矩阵

ACwing 4081. 选数

[AcWing 116]飞行员兄弟 题解

ACwing 题解 [66.两个链表的第一公共结点](Cpp)

3.10前缀和与差分

标签