AcWing 1913. 公平摄影
原题链接
简单
服了, 一个是点的前缀和, 一个是线段的前缀和, 终究是不明白的…哭泣…
熟悉哈希, 和找连续段
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n;
PII q[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
int x;
char str[2];
scanf("%d%s", &x, str);
if (*str == 'G') q[i] = {x, 1};
else q[i] = {x, -1};
}
sort(q + 1, q + n + 1);
unordered_map<int, int> hash;
int res = 0, sum = 0, last;
for (int i = 1; i <= n; i ++ )
{
if (!hash.count(sum)) hash[sum] = q[i].x;
sum += q[i].y;
if (hash.count(sum)) res = max(res, q[i].x - hash[sum]);
if (i == 1 || q[i].y != q[i - 1].y) last = q[i].x;
res = max(res, q[i].x - last);
}
printf("%d\n", res);
return 0;
}