hihoCoder 1123-好配对 #1123 : 好配对 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 给定两个序列a和b，每个序列中可能含有重复的数字。 一个配对(i,j)是一个好配对当从第一个序列中选出一个数ai，再从第二个序列中选出一个数bj且满足ai>bj。 给出两个序列，问存在多少个好配对。 输入 输入包含多组数据，数据第一行一个整数T，表示数据组数。(T<=5) 每组数据第一行包含两个整数n和m。(0<n,m<=$$10^5$$) 接下来n行，每行两个整数x和y，表示在第一个序列中有y个x。 接下来m行，每行两个整数x和y，表示在第二个序列中有y个x。(0<x<=$$10^9$$,0<y<=$$10^4$$) 输出 对于每组数据，输出一行一个整数，表示好配对的数量 样例输入 1 2 2 3 2 4 1 3 1 2 3 样例输出 10
此题最先想到的解法是类似桶排序的思路，用空间来换时间，但是看到x的范围是$$10^9$$，显然不行，于是牺牲时间来换空间，构造： [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。]]>