@3-2 optimal threshold of CCF 2020-12-2 final forecast

Title Description

Input and output

Examples

Source code

#include<iostream>
#include<algorithm>
using namespace std;
pair<int, int> n[100005];      // Every pair Store a classmate's y and result
int re0[100005];               // Record the position and the previous result by 0 The number of 
int re1[100005];              // Record the position and the following result by 1 The number of 
int num = -1,v = 0;              //num Used to record the number of successes  v To record the best threshold 
int main() {
    
    int m;
    cin >> m;                     
    n[0] = pair<int, int>(-1, -1);
    for (int i = 1; i <= m; ++i)   
        cin >> n[i].first >> n[i].second;
    sort(n + 1, n + 1 + m);  // Sort the thresholds from small to large   No row n[0] Because we initialize it to -1  And we are directly from n[1] Start taking 
    for (int i = 1; i <= m; ++i)            // Because it does not include the current number 0 Of   So take re0[i-1]
        if (n[i].second == 0)
            re0[i] = re0[i - 1] + 1;
        else
            re0[i] = re0[i - 1];
    for (int i = m; i >= 1; --i)           // Because it includes the current number 1  So just use re1[i] that will do 
        if (n[i].second == 1)
            re1[i] = re1[i + 1] + 1;
        else
            re1[i] = re1[i + 1];
    for (int i = 1; i <= m; ++i) {
              
        if (n[i].first == n[i - 1].first)
            continue;                   // If there is yi  The same thing   The threshold has been used 1 Time   You don't have to take it again   You can skip 
        if (num <= re0[i - 1] + re1[i])
            num = re0[i - 1] + re1[i], v = n[i].first;
    }
    cout << v;
    return 0;
}

About this problem

The title explains ：

So violence traverses Can finish 70% Last 30% It's likely to timeout
So let's optimize here

          0     1 （ Threshold access ）  
pre       1     0         re     0
          1     1                0
          1     1                1
          1     1                1
          1     1                1
          1     1                1
  After ascending   The number before the threshold  pre All for 0  The latter number includes himself  pre All for 1
          So in fact, we only need statistics   Before the threshold 0 The number and the following include itself 1 The number of 
          Here I give an example 1 Medium threshold access 0  and  1  Example   
         0 The last four 1  There is no 0  The total is 4   Results and re The same number is 1
         1 The last four 1  front 1 individual 0   Summed up in 5    The results are also consistent 

Every pair Store a classmate's y and result
re0 Array is used to record the position and the previous result by 0 The number of
re1 The array records the position and the following result by 1 The number of
num Used to record the number of successes v To record the best threshold
num = re0[i - 1] + re1[i]
It's written because Access time Does not include the current location 0 Including the current location 1