6. 青蛙与蚊子byHNU信息院2020通信小毕
日期: 2020-12-13 分类: 跨站数据测试 519次阅读
【问题描述】
有 n 只青蛙位于坐标轴 OX 上,对于每只青蛙,有两个已知值 xi、ti,表示第 i 只青蛙在坐标的位置(各不相同)以及它的舌头的长度。同样有 m 只蚊子一只接一只的落到坐标轴上,对于每只蚊子,有两个已知值, pj 表示第 j 只蚊子所在的位置,bj 为第 j 只蚊子的重量。青蛙和蚊子表示为坐标上的点。如果蚊子和青蛙在同一位置或者在右边,青蛙可以吃掉蚊子,它们之间的距离不超过青蛙舌头的长度。如果有几只青蛙都能在某一时刻吃到一只蚊子,最左边的青蛙就会吃掉它(最小的 xi)。吃完蚊子后,青蛙的舌头将增加蚊子重量的长度,在之后,青蛙又能够吃其他蚊子(在舌头长度增加之后)。
在所有蚊子落下以及青蛙吃掉所有可能的蚊子之后,对于每个青蛙,输出两个值,即吃蚊子的数量以及舌头的长度。 每只蚊子只有在青蛙吃完之前所有可能的蚊子之后才会落到坐标上,蚊子的值是按其落到坐标轴上的顺序给出的。如果蚊子和青蛙在同一位置或者在右边,青蛙可以吃掉蚊子,它们之间的距离不超过青蛙舌头的长度。 如果有几只青蛙都能在某一时刻吃到一只蚊子,最左边的青蛙就会吃掉它(最小的 xi)。吃完蚊子后,青蛙的舌头将增加蚊子重量的长度,在之后,青蛙又能够吃其他蚊子(在舌头长度增加之后)。 在所有蚊子落下以及青蛙吃掉所有可能的蚊子之后,对于每个青蛙,输出两个值,即吃蚊子的数量以及舌头的长度每只蚊子只有在青蛙吃完之前所有可能的蚊子之后才会落到坐标上,蚊子的值是按其落到坐标轴上的顺序给出的。
【输入形式】
输入的第一行为两个整数(1 ≤ n,m ≤ 2*105),表示青蛙和蚊子的数量。
接下来的 n 行,每行两个整数 xi、ti(0 ≤ xi、ti ≤ 109),表示第 i 只青蛙所在的位置以及它的舌头的初始长度,输入保证所有的 xi 互不相同。
接下来的 m 行,每行两个整数 pj、bj(0 ≤ pj、bj ≤ 109),表示第 j 只蚊子落下的位置以及它的重量。
【输出形式】
输出为 n 行,第 i 行包含另两个整数值 ci、li,表示被第 i 只青蛙吃掉的蚊子数量以及最终的青蛙的舌头长度。
【样例输入1】
4 6
10 2
15 0
6 1
0 1
110 10
1 1
6 0
15 10
14 100
12 2
【样例输出1】
3 114
1 10
1 1
1 2
【样例输入2】
1 2
10 2
20 2
12 1
【样例输出2】
1 3
【样例说明】
【评分标准】
来了来了,点个赞加关注,是我前行下去的动力,也可以在HNU2020本科信息群里面搜出我,唯一一个姓毕的,HNU信息院2020的通信小毕会和你一起努力的
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct frog {
int x;
int t;
int shu = 0;
int num;
};
struct wenzi {
int p;
int b;
int bei;
bool live = true;
};
bool c1(frog a, frog b)
{
return a.x< b.x;
}
bool c2(frog a, frog b)
{
return a.num< b.num;
}
int main()
{
long long int n,m;
cin >> n >> m;
frog* f = new frog[n];
wenzi* w = new wenzi[m];
for (int i = 0; i < n; i++)
{
cin >> f[i].x >> f[i].t;
f[i].num = i + 1;
}
for (int i = 0; i < m; i++) {
cin >> w[i].p >> w[i].b;
}
sort(f, f + n, c1);
for (int a = 0; a < m; a++)
{
for (int b = 0; b < n; b++)
if (f[b].x + f[b].t >= w[a].p && f[b].x<= w[a].p && w[a].live)
{
f[b].t += w[a].b;
f[b].shu++;
w[a].live= false;
a = -1;
break;
}
}
sort(f, f + n, c2);
for (int i = 0; i < n; i++) {
cout << f[i].shu << " " << f[i].t << endl;;
}
return 0;
}
除特别声明,本站所有文章均为原创,如需转载请以超级链接形式注明出处:SmartCat's Blog
标签:OG c++
上一篇: 手把手带你入门Python爬虫(二、爬虫预备知识)
下一篇: 使用pip管理Python包
精华推荐