#1123 : 好配对

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

描述

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

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

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

输入

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

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

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

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

输出

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

样例输入
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=; i<n; i++)
{
scanf("%d %d", &a[i].x, &a[i].y);
}
for(i=; i<m; i++)
{
scanf("%d %d", &b[i].x, &b[i].y);
}
sort(a, a+n);
sort(b, b+m);
long long int cnt=;
long long int sum=;
j=;
for(i=; 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\n", sum );
}
return ;
}

最新文章

  1. 重启Ubuntu后Hadoop的namenode起不来的解决办法‬
  2. POJ3687 Labeling Balls(拓扑排序\贪心+Floyd)
  3. 关于职位的解释---转CSDN的文章
  4. 【HTTP】POST 与 PUT 方法区别
  5. 压缩html 减小存储空间
  6. thinkPHP 视图
  7. Matlab: 作图
  8. 关于UIButton嵌入到UIView点击无反应问题的解决方法和delegate的简单用法示例(转载)
  9. maven私服上传jar包
  10. 小程序自定义pick(日期加时间组合)
  11. volatile关键字作用
  12. 最长(大)回文串的查找(字符串中找出最长的回文串)PHP实现
  13. Codeforces Round #418 (Div. 2)
  14. 【BZOJ2940】条纹(博弈论)
  15. Confluence 6 代理和 HTTPS 设置连接器
  16. Jenkins解决无法获取插件的办法(升级站点目录)
  17. KMP 算法详解
  18. 列式存储hbase系统架构学习
  19. poj2387 Til the Cows Come Home(Dijkstra)
  20. JavaScript简述一

热门文章

  1. (4)Unity3d镜头
  2. U盘格式化时分配单元的大小的设置
  3. Window10下Apache2.4的安装和运行
  4. Git安装及SSH Key管理之Mac篇
  5. 合并SO为单独交货单
  6. generate alphanumeric serial number
  7. Android中Environment与StatFs获取系统/SDCard存储空间大小
  8. smali语法(一)
  9. 使用Python与数据库交互
  10. mongodb查看连接数、同步时间、oplog及修改表名的操作