4.28招商fintech第一题 离散化差分

#include<iostream>
#include<vector>
#include <map>
#include <algorithm>
using namespace std;
const int N = 2010;
int a[N], b[N]; //差分数组a, 前缀和数组b
int n, t, res = N;
typedef pair<int, int> PII;
vector<int> all;//所有端点
map<int, int> alls;//离散化端点
vector<PII> diff;//所有区间端点对


int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        int x, y;
        char c;
        cin >> c >> x;
        if(c == 'G') y = 1e9, diff.push_back({x,y});
        else y = 0, diff.push_back({y,x});
        all.push_back(x);
        all.push_back(y);
    }
    //排序加去重
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end()); 
    //map中离散化
    for(auto tmp : all){
        alls[tmp] = ++t;
    }
    //差分
    for(auto tmp : diff){
        int l = alls[tmp.first], r = alls[tmp.second]; 
        a[l] ++, a[r + 1] --;
    }
    //前缀和
    for (int i = 1; i <= alls.size(); i ++ ){
        b[i] = b[i - 1] + a[i];
        res = min(res, n - b[i]);
    }
    cout << res << endl;
    return 0;
}