hihocoder 挑战赛9 A.好配对(思维题目 防止超时)
2024-08-23 07:33:47
#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 ;
}
最新文章
- 重启Ubuntu后Hadoop的namenode起不来的解决办法
- POJ3687 Labeling Balls(拓扑排序\贪心+Floyd)
- 关于职位的解释---转CSDN的文章
- 【HTTP】POST 与 PUT 方法区别
- 压缩html 减小存储空间
- thinkPHP 视图
- Matlab: 作图
- 关于UIButton嵌入到UIView点击无反应问题的解决方法和delegate的简单用法示例(转载)
- maven私服上传jar包
- 小程序自定义pick(日期加时间组合)
- volatile关键字作用
- 最长(大)回文串的查找(字符串中找出最长的回文串)PHP实现
- Codeforces Round #418 (Div. 2)
- 【BZOJ2940】条纹(博弈论)
- Confluence 6 代理和 HTTPS 设置连接器
- Jenkins解决无法获取插件的办法(升级站点目录)
- KMP 算法详解
- 列式存储hbase系统架构学习
- poj2387 Til the Cows Come Home(Dijkstra)
- JavaScript简述一