本文介绍: 在所有蚊子落下以及青蛙吃掉所有可能蚊子之后,对于每个青蛙输出两个值,即吃蚊子的数量以及舌头长度。每只蚊子只有在青蛙吃完之前所有可能蚊子之后才会落到坐标上,蚊子的值是按其落到坐标轴上的顺序给出的。如果蚊子和青蛙在同一位置或者在右边青蛙可以吃掉蚊子,它们之间距离不超过青蛙舌头长度。吃完蚊子后,青蛙的舌头将增加蚊子重量长度,在之后,青蛙能够吃其他蚊子(在舌头长度增加之后)。只青蛙所在的位置以及它的舌头的初始长度输入保证所有的。只青蛙吃掉的蚊子数量以及最终的青蛙的舌头长度

问题描述

       有 n 只青蛙位于坐标轴 OX 上,对于每只青蛙,有两个已知值 xiti表示 i 只青蛙在坐标位置(各不相同)以及它的舌头的长度。同样有 m 只蚊子一只接一只的落到坐标轴上,对于每只蚊子,有两个已知值, pj 表示第 j 只蚊子所在的位置bj 为第 j 只蚊子的重量。青蛙和蚊子表示为坐标上的点。

       如果蚊子和青蛙在同一位置或者在右边,青蛙可以吃掉蚊子,它们之间距离不超过青蛙舌头的长度

       如果有几只青蛙都能在某一时刻吃到一只蚊子,最左边的青蛙就会吃掉它(最小的 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 包含另两个整数值 cili表示被第 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

【样例说明
评分标准

要对蚊子顺序排队,要把能先吃的吃了,再看隔得远的能不能吃到

#include<iostream>
#include<algorithm>
using namespace std;
struct wq
{
	int w;//位置 
	int z;//长度或者质量 
	int cnt=0;//吃的蚊子数量 
}q[200005],w[200005];
bool cmp(wq x,wq y)
{
	return x.w<y.w;
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>q[i].w>>q[i].z;
	for(int i=0;i<m;i++)cin>>w[i].w>>w[i].z;
	sort(w,w+m,cmp);
	for(int i=0;i<m;i++)//蚊子循环 
	{
		int ma=-1,temp=-1;//ma记录最大距离temp记录最小出现的位置 
		for(int j=0;j<n;j++)//青蛙循环 
		{
			if(q[j].w<=w[i].w&amp;&amp;q[j].z>=w[i].w-q[j].w)
			{
				if(ma<w[i].w-q[j].w) ma=w[i].w-q[j].w,temp=j;
			}
		}
		if(temp!=-1) q[temp].z+=w[i].z,q[temp].cnt++;
	}
	for(int i=0;i<n;i++) cout<<q[i].cnt<<" "<<q[i].z<<endl;
}

原文地址:https://blog.csdn.net/2203_75441856/article/details/134763931

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_39198.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注