hihocoder 挑战赛9 A.好配对（思维题目 防止超时）

#1123 : 好配对

时间限制:1000ms

单点时限:1000ms

内存限制:256MB

描述

给定两个序列a和b，每个序列中可能含有重复的数字。

一个配对(i,j)是一个好配对当从第一个序列中选出一个数a_i，再从第二个序列中选出一个数b_j且满足a_i>b_j。

给出两个序列，问存在多少个好配对。

输入

输入包含多组数据，数据第一行一个整数T，表示数据组数。(T<=5)

每组数据第一行包含两个整数n和m。(0<n,m<=10⁵)

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

接下来m行，每行两个整数x和y，表示在第二个序列中有y个x。(0<x<=10⁹,0<y<=10⁴)

输出

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

样例输入

1
2 2
3 2
4 1
3 1
2 3

样例输出

10

算法：O（n）的复杂度
代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include <queue>
#include <algorithm>
#define N 100000+10

using namespace std;
int n, m;
struct nodea
{
    int x, y;
    bool operator < (const nodea&dd)const
    {
        return x<dd.x;
    }
}a[N];

struct nodeb
{
    int x, y;
    bool operator < (const nodeb&dd)const
    {
        return x<dd.x;
    }
}b[N];


int main()
{
    int t;
    int i, j;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d", &n, &m);
        for(i=0; i<n; i++)
        {
            scanf("%d %d", &a[i].x, &a[i].y);
        }
        for(i=0; i<m; i++)
        {
            scanf("%d %d", &b[i].x, &b[i].y);
        }
        sort(a, a+n);
        sort(b, b+m);
        long long int cnt=0;
        long long int sum=0;
        j=0;
        for(i=0; i<n; i++)
        {
            while(a[i].x > b[j].x && j<m )
            {
                cnt+=b[j].y;
                j++;
            }
            sum=sum+cnt*a[i].y;
            //printf("%lld---", sum );
        }
        printf("%lld
", sum );
    }
    return 0;
}