11526: 【原1526】好配对

题目

题目描述

author: 金耀楠原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1526 ## Description

给定两个序列a和b，每个序列中可能含有重复的数字。一个配对(i,j)一个好配对当从第一个序列中选出一个数ai，再从第二个序列中选出一个数bj且满足ai>bj。给出两个序列，问存在多少个好配对。

Input Format

输入包含多组数据，数据第一行一个整数T，表示数据组数。每组数据第一行包含两个整数n和m。

接下来n行，每行两个整数x和y，表示在第一个序列中有y个x。接下来m行，每行两个整数x和y，表示在第二个序列中有y个x。

Output Format

对于每组数据，输出一行一个整数，表示好配对的数量

Sample Input

Sample Output

Hint

单点时限:1000ms 内存限制:256MB

yyong119's solution

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_N = 100010;
struct node {
    int key, num;
};
node a[MAX_N], b[MAX_N];
int Case;

inline bool cmp(node p, node q) { return p.key < q.key; }

int main() {

    scanf("%d", &Case);
    while (Case--) {

        long long ans = 0;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; ++i) scanf("%d%d", &a[i].key, &a[i].num);
        for (int i = 0; i < m; ++i) scanf("%d%d", &b[i].key, &b[i].num);
        sort(a, a + n, cmp);
        sort(b, b + m, cmp);

        int j = 0; long long sum = 0;
        for (int i = 0; i < n; ++i) {
            for (; j < m; ++j) {
                if (a[i].key > b[j].key)
                    sum += b[j].num;
                else break;
            }
            ans += sum * a[i].num;
        }
        printf("%lld\n", ans);
    }
    return 0;
}