Table of contents: Algorithm Diary

1913 fair Photography – AcWing question bank

Topic describes

Farmer John’s NNN cow stands on different sides of a long one-dimensional fence.

The third cow is located at location XIx_ ixi and belongs to the breed BIB_ibi (Guernsey or Holstein).

All cows are in different positions.

John wanted to take a photograph of a continuous section of cows for display at a country fair.

But we want all of his cows to be fairly represented in the photos.

So he wanted to make sure that no matter what breeds of cows were in the photo, there had to be an equal number of each breed in the photo.

For example, it is ok to include only Holsteins in a photo, 272,727 holsteins and 999 Guernsey, but not 101,010 Holsteins and 999 Guernsey.

Please determine the maximum size of a photo that John can take that meets the above criteria.

The size of the photo refers to the difference between the largest and smallest position of the cow in the photo.

John may end up taking only one cow, in which case the image size is 000.

Input format

The first line contains the integer NNN.

Next up are NNN lines, each containing an integer xix_ixi and a character BIB_ibi (HHH for Holstein cow and GGG for Guernsey cow).

The output format

Output the maximum size of the photo.

Data range


  • 1 Or less N Or less 1 0 5 1 N or less 10 ^ 5 or less

  • 0 Or less x i Or less 1 0 9 0 or less x_i 10 ^ 9 or less

Enter the sample

6
4 G
10 H
7 G
16 G
1 G
3 H
Copy the code

The output sample

7
Copy the code

Algorithm ideas

The maximum picture size to meet the requirements of the topic is as follows:

  1. Contains only HHH Holstein cattle;
  2. Contains only GGG Guernsey cattle;
  3. Contains an equal number of HHH Holstein and GGG Guernsey cattle;

Case (3) is more complicated, so consider how to deal with it first. ±1±1±1 can be used to represent the types of cattle respectively for convenient processing. When the types of cattle covered by the size of the picture and sum==0sum ==0sum ==0, the number of cattle is equal. The input sequence is out of order, so the input data must be sorted according to coordinates.

Through the above operations, we can get the maximum photo size by violent traversal, but the time complexity is O(n2)O(n^2)O(n2), consider optimization.

Since size is defined as the difference between the maximum and minimum position, we need to record a minimum position. When the sumsumsum of the current position is equal to the sumsumsum of the minimum position (i.e. the number of cattle between the current position and the minimum position is equal), the photo is a legal photo and has a size maximum. The minimum position is the position where sumsumsum first appears.

There is a detail here. The sum of cattle species is actually used as prefix sum, which is calculated as sumr− SUML − 1SUM_R-sum_ {L-1}sumr− SUML −1, and the required photo size should be R − LR-LR − L. Therefore, when storing the minimum location (the left endpoint), the prefix sum should be in the range of [0, L −1][0, L-1][0, L −1], but in judgment, the prefix sum range is [0,r][0, r][0,r] [0, R].

For the situation (1) and (2), there may also be a maximum size photo. Save and update the minimum position of cattle of the same breed, and judge by violence.

AC code

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
pair<int.int> nums[N];
map<int.int> dic;
int n;
int main(a) {
    cin>>n;
    for(int i = 1; i <= n; ++i) {
        int x;
        char b;
        cin>>x>>b;
        if(b == 'G') nums[i] = {x, 1};
        else nums[i] = {x, - 1};
    }
    sort(nums + 1, nums + 1 + n);
    
    int last = 0; // Same breed
    int sum = 0; // Different varieties
    int res = 0;
    for(int i = 1; i <= n; ++i) {
        // Add minimum position without nums[I]
        if(! dic.count(sum)) dic[sum] = nums[i].first; 
        // compare prefix and, including nums[I]
        sum += nums[i].second;
        if(dic.count(sum)) res = max(res, nums[i].first - dic[sum]); 
        
        // Same breed
        if(i == 1|| nums[i].second ! = nums[i -1].second) last = nums[i].first;
        res = max(res, nums[i].first - last);
    }
    cout<<res<<endl;
    return 0;
}
Copy the code