2 条题解

  • 4
    @ 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;
    }
    
    • 0
      @ 2026-4-18 17:50:13

      #include #include #include

      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
      难度
      2
      标签
      递交数
      141
      已通过
      85
      上传者