网站怎么做分类聚合,网站建设咨询有客诚信,百度搜索百度,电子商务网站建设分析论文【问题描述】 有 n 只青蛙位于坐标轴 OX 上#xff0c;对于每只青蛙#xff0c;有两个已知值 xi、ti#xff0c;表示第 i 只青蛙在坐标的位置#xff08;各不相同#xff09;以及它的舌头的长度。同样有 m 只蚊子一只接一只的落到坐标轴上#xff0c;对于每只蚊子#x…【问题描述】 有 n 只青蛙位于坐标轴 OX 上对于每只青蛙有两个已知值 xi、ti表示第 i 只青蛙在坐标的位置各不相同以及它的舌头的长度。同样有 m 只蚊子一只接一只的落到坐标轴上对于每只蚊子有两个已知值 pj 表示第 j 只蚊子所在的位置bj 为第 j 只蚊子的重量。青蛙和蚊子表示为坐标上的点。 如果蚊子和青蛙在同一位置或者在右边青蛙可以吃掉蚊子它们之间的距离不超过青蛙舌头的长度。 如果有几只青蛙都能在某一时刻吃到一只蚊子最左边的青蛙就会吃掉它最小的 xi。吃完蚊子后青蛙的舌头将增加蚊子重量的长度在之后青蛙又能够吃其他蚊子(在舌头长度增加之后)。 在所有蚊子落下以及青蛙吃掉所有可能的蚊子之后对于每个青蛙输出两个值即吃蚊子的数量以及舌头的长度。 每只蚊子只有在青蛙吃完之前所有可能的蚊子之后才会落到坐标上蚊子的值是按其落到坐标轴上的顺序给出的。
【输入形式】 输入的第一行为两个整数(1 ≤ nm ≤ 2*105表示青蛙和蚊子的数量。 接下来的 n 行每行两个整数 xi、ti0 ≤ xi、ti ≤ 109表示第 i 只青蛙所在的位置以及它的舌头的初始长度输入保证所有的 xi 互不相同。 接下来的 m 行每行两个整数 pj、bj0 ≤ 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 #includeiostream
#includealgorithm
using namespace std;
struct frog {int pos;int len;int eat 0;int index;
};
struct mosquito {int pos;int weight;bool live 1;
};
bool cmp1(frog a, frog b) { //按位置排列return a.pos b.pos;
}
bool cmp2(frog a, frog b) { //最后按顺序输出return a.index b.index;
}
int main() {int n, m;cin n m;frog frogs[n];mosquito mosquitoes[m];for (int i 0; i n; i) {cin frogs[i].pos frogs[i].len;frogs[i].index i;}for (int i 0; i m; i) {cin mosquitoes[i].pos mosquitoes[i].weight;}sort(frogs,frogsn,cmp1);for (int i 0; i m; i) {for (int j 0; j n; j) {if (mosquitoes[i].live frogs[j].pos frogs[j].len mosquitoes[i].posfrogs[j].posmosquitoes[i].pos) {frogs[j].eat;frogs[j].len mosquitoes[i].weight;mosquitoes[i].live 0;i-1;break;}}}sort(frogs,frogsn,cmp2);for(int i0;in;i){coutfrogs[i].eat frogs[i].lenendl;}return 1;
}
