1 条题解

  • 1
    @ 2021-8-7 19:00:37

    C++ :

    #include <iostream>
    #include <algorithm>
    #include <set>
    
    using namespace std;
    
    typedef long long LL;
    typedef pair<int, int> PII;
    const int N = 100010;
    
    int n, m;
    PII mchs[N], tasks[N];
    
    int main()
    {
        while(cin >> n >> m)
        {
            for(int i = 0; i < n; i++) cin >> mchs[i].first >> mchs[i].second;
            for(int i = 0; i < m; i++) cin >> tasks[i].first >> tasks[i].second;
            
            sort(mchs, mchs + n);
            sort(tasks, tasks + m); //从小到大排序
            
            multiset<int> ys; //可以用相同元素
            LL cnt = 0, res = 0;
            for(int i = m - 1, j = n - 1; i >= 0; i--) //从大到小遍历 i枚举任务,j枚举机器
            {
                int x = tasks[i].first, y = tasks[i].second;
                while(j >= 0 && mchs[j].first >= x) ys.insert(mchs[j --].second); //横坐标大于等于当前任务的机器加入set
                auto it = ys.lower_bound(y); //>=当前任务y值的最小y
                if(it != ys.end())
                {
                    cnt ++;
                    res += 500 * x + 2 * y;
                    ys.erase(it); // 删掉机器
                }
            }
            cout << cnt << ' ' << res <<endl;
        }
        return 0;
    }
    
    • 1

    信息

    ID
    38
    时间
    1000ms
    内存
    128MiB
    难度
    1
    标签
    递交数
    72
    已通过
    54
    上传者