Luobuyu's Blog

0%

1913.公平摄影

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 2k 阅读时长 ≈ 2 分钟
好像见过这种题目，需要使用哈希的。

1913. 公平摄影

题目描述：

农夫约翰的 $ N $ 头奶牛站在一维长围栏的不同位置。

第 $ i $ 头牛位于位置 $ x_i $ ，其所属品种为 $ b_i $ （根西岛牛或荷斯坦牛）。

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

约翰想给一段连续区间内的奶牛拍摄一张照片，用来在乡村集市上展览。

但是我们希望他所有品种的奶牛都能在照片中得到公平的展示。

因此，他希望确保无论照片中出现哪些品种的奶牛，每种品种的奶牛在照片中的数量都必须相等。

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

请确定，约翰可以拍下的满足以上条件的照片的最大尺寸。

照片的尺寸是指照片中奶牛最大和最小位置之间的差。

约翰最终可能只拍下一头奶牛，这种情况下，照片尺寸为 $ 0 $ 。

输入格式

第一行包含整数 $ N $ 。

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

输出格式

输出照片的最大尺寸。

数据范围

输入样例：

1
2
3
4
5
6
7
6
4 G
10 H
7 G
16 G
1 G
3 H

输出样例：

1
7

样例解释

共 $ 6 $ 头牛，从左到右排列顺序为 G,H,G,G,H,G。

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

题解：

注意是让求坐标差，而不是个数。

比较容易想到的是一个计为 $ 1 $ ，另一个计为 $ -1 $ 。这样的话相等数量只需要看区间和为 $ 0 $ 的就行了。但是如果枚举每一段区间的话需要 $ O(n^2) $ ，直接炸了。需要考虑优化。我们需要找到每个位置 $ i $ ，他的前缀和为 $ sum[i] $ ，他的前面距离他最远的一个位置 $ j $ ，位置 $ j $ 的前缀和也为 $ sum[i] $ 。可以存下来。然后每次直接查找，还需要复杂度小于 $ O(n) $ ，想到使用 hash。可以直接使用 unorder_map<int, int> mp 用 mp[i] = pos 表示前缀和为 i 的最前面的位置。需要注意的是 s = sum[i] - sum[j-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
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
vector<PII> a;
int sum[maxn];
unordered_map<int, int> mp;
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int x;
    char ch;
    a.push_back({-1, 0});
    for (int i = 1; i <= n; i++)
    {
        cin >> x >> ch;
        a.push_back({x, ch == 'G' ? 1 : -1});
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < a.size(); i++)
    {
        sum[i] = a[i].second;
    }
    int ans = 0;
    mp[0] = 0;
    int last;
    int flag = 1;
    for (int i = 1; i <= n; i++)
    {
        if (i == 1 || a[i].second != a[i - 1].second)
        {
            last = a[i].first;
        }
        ans = max(ans, a[i].first - last);
        sum[i] += sum[i - 1];
        if (!mp.count(sum[i]))
        {
            mp[sum[i]] = i;
        }
        else
        {
            ans = max(ans, a[i].first - a[mp[sum[i]] + 1].first);
        }
    }

    cout << ans << endl;
    return 0;
}