NOIP series

What is discretization in c + +?

Take a look at the example first

Given the number of n (possibly the same), how many times does the most frequent number occur. (n<= 10 ^ 9)

Um... This problem looks like a water problem. Just open a V array to record the number of times each number appears, such as v[a[i]] + +. However, it is worth noting that ai may be very large, which will cause the vis array cannot be opened, so discretization is needed.

In general, discretization is the compression of a string of numbers
For example, G [1] = 1 g [2] = 3 G [3] = 100000 G [4] = 45
After discretization, G [1] = 1g [2] = 2G [3] = 4g[4] = 3. At this time, g[i] stores each number in the size position of all numbers. Among the above, 45 is the third largest, so the original g[4] of 45 becomes 3. In this way, the example is easy to do, because at this time, G is equivalent to vis array, and the maximum length of this array must be less than or equal to n. (there may be duplicate numbers) by the way, if you want to keep the original number, just open another array record.

How to realize discretization?

There are two ways

1.

First, we need to open a structure to record the initial value of each number and its position in the array. Then create a pointer that represents the number of different numbers.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, a[10005], g[10005];    //g [] to store value 
struct node
{
    int num, id;
    bool operator < (const node& other)const
    {
        return num < other.num;        //Default from small to large 
    }
}t[maxn];
int now = 0;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i){t[i].num = a[i]; t[i].id = i;}
    sort(t + 1, t + n + 1);        //To discrete, sort first 
    for(int i = 1; i <= n; ++i)
    {
        if(i == 1 || t[i].num != t[i].num) now++;    //If it's a different number from the previous one, now + + (because it's already ordered) 
        g[now] = t[i].num; a[t[i].id] = now;        //What a[i] stores at this time is that a[i] is the smallest number 
    }
    for(int i = 1; i <= n; ++i) printf("%d ", a[i]);
    printf("\n");
    for(int i = 1; i <= n; ++i) printf("%d ", g[i]);
    printf("\n");
    return 0;
}

Input:

5

2 100 4 1 4

Output:

2 4 3 1 3

1 2 4 100

At this point, we can also find that the pointer now not only indicates that there are different numbers of now, but also indicates what the number with the smallest now is

A little change is the example

#include <bits/stdc++.h>
using namespace std;
int n, a[100005], g[100005], tot[100005];    
bool cmp(int a, int b)
{
    return a > b;
}
struct node
{
    int num, id;
    bool operator < (const node& other)const
    {
        return num < other.num;    
    }
}t[maxn];
int now = 0;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i){t[i].num = a[i]; t[i].id = i;}
    sort(t + 1, t + n + 1);        
    for(int i = 1; i <= n; ++i)
    {
        if(i == 1 || t[i].num != t[i - 1].num) now++;    
        g[now] = t[i].num; a[t[i].id] = now;        
    }
    for(int i = 1; i <= n; ++i) tot[a[i]]++;
    sort(tot + 1, tot + n + 1, cmp);
    printf("%d\n", tot[1]);
    return 0;
}

2.

This approach is what I learned recently. It is not only simple in idea, but also convenient to implement.

First of all, we store all the numbers in an array, then arrange them in order, then de duplicate them (using the unique function). Finally, we find the position of each number by using lower bound, that is, the discretized value.

#include <bits/stdc++.h>
using namespace std;
int a[100005], t[100005];
int main()
{
    int n; scanf("%d", &n); 
    for(int i = 1; i <= n; ++i) {scanf("%d", &a[i]); t[i] = a[i];}
    sort(a + 1, a + n + 1);
    int _n = unique(a + 1, a + n + 1) - a - 1;         
    for(int i = 1; i <= _n; ++i)
        t[i] = lower_bound(a + 1, a + _n + 1, t[i]) - a;
    for(int i = 1; i <= n; ++i) printf("%d ", t[i]);
    return 0;
}

Input:

7

1 2 8 4 6 4 100

Output:

1 2 5 3 4 3 100

Finally, we still want to emphasize that discretization, please be sure to master!!!

Source: https://me.csdn.net/qq_43058710