hihoCoder 1123-好配对
#1123 : 好配对
时间限制:1000ms
单点时限:1000ms
内存限制:256MB
描述
给定两个序列a和b，每个序列中可能含有重复的数字。
一个配对(i,j)是一个好配对当从第一个序列中选出一个数ai，再从第二个序列中选出一个数bj且满足ai>bj。
给出两个序列，问存在多少个好配对。
输入
输入包含多组数据，数据第一行一个整数T，表示数据组数。(T<=5)
每组数据第一行包含两个整数n和m。(0<n,m<=)
接下来n行，每行两个整数x和y，表示在第一个序列中有y个x。
接下来m行，每行两个整数x和y，表示在第二个序列中有y个x。(0<x<=,0<y<=)
输出
对于每组数据，输出一行一个整数，表示好配对的数量
样例输入
1
2 2
3 2
4 1
3 1
2 3
样例输出
10
此题最先想到的解法是类似桶排序的思路，用空间来换时间，但是看到x的范围是，显然不行，于是牺牲时间来换空间，构造：
[cpp]
typedef struct Ele
{
int value;
int num;
bool operator < (const Ele& e) const
{
return value < e.value;
}
};
[/cpp]
依次输入两个序列，并按value从小到大排序；两个序列从头开始遍历，计算好配对的个数。
完整代码如下：
[cpp]
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef struct Ele
{
int value;
int num;
bool operator < (const Ele& e) const
{
return value < e.value;
}
};
vector<Ele> first_seq, second_seq;
int main()
{
int t,m,n,x,y;
long long ans;
scanf("%d", &t);
while (t–)
{
scanf("%d %d", &n, &m);
first_seq.clear();
first_seq.resize(n);
second_seq.clear();
second_seq.resize(m);
for (int i = 0; i < n; i++)
scanf("%d %d", &first_seq[i].value, &first_seq[i].num);
for (int i = 0; i < m; i++)
scanf("%d %d", &second_seq[i].value, &second_seq[i].num);
sort(first_seq.begin(), first_seq.end());
sort(second_seq.begin(), second_seq.end());
ans = 0;
int i = 0, j = 0;
long long sum2 = 0;
while (i < n && j < m)
{
while (j < m && second_seq[j].value < first_seq[i].value)
{
sum2 += second_seq[j].num;
j++;
}
ans += (first_seq[i].num*sum2);
i++;
}
while (i < n)
{
ans += (first_seq[i].num*sum2);
i++;
}
printf("%lldn", ans);
}
return 0;
}
[/cpp]
本代码提交AC，用时193MS，内存11MB。]]>