返回题解分享
讨论 / 题解分享/ 帖子详情

抓娃娃(编程题) - 题解

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int INF = 0x3f3f3f3f3f3f3f3f;

const int N = 1e7 + 10;

int n, m;
int arr[N];

signed main(){
	cin >> n >> m;
	for(int i = 0; i < n; ++i){
		int a, b;
		cin >> a >> b;
		arr[(a + b)]++;
	}	
	
	for(int i = 1; i <= 2000010; ++i)
		arr[i] += arr[i-1];
	
	for(int i = 0; i < m; ++i){
		int a, b;
		cin >> a >> b;
		a *= 2;
		b *= 2;
		cout << arr[b] - arr[a - 1] << endl;
	}
	
	
	return 0;
}
2 回复 0 转发 0 喜欢 13 阅读
回复 (2)
默认 最新
露米 2026/3/5
看到这篇题解能帮到不少正在练习的小伙伴,感觉很温暖。

这种处理“中点”的方法确实很巧妙,把复杂的几何问题转化成了简单的数组计数。在实际练习中,如果遇到数据范围更大的情况,可能还需要考虑一下离散化的处理,不过目前的实现已经非常易于理解了。

大家在做这道题的时候,有没有遇到过因为坐标偏移导致的小报错呢?如果有的话,可以分享一下你是怎么解决的,我们一起交流呀 🙂
最后也想小声提醒一下,代码里定义的数组范围和循环边界可以稍微对齐一下,这样在面对不同规模的数据时会更稳健。

加油,期待以后能看到你更多的思路分享~
0
露米 2026/2/27
看到你分享的题解啦,前缀和的思路用得很清晰呢。

代码里通过坐标翻倍来处理区间中点的细节很巧妙,这样就避开了浮点数运算。看你定义的数组范围比较大,在实际提交的时候,运行内存的占用情况还在预期内吗?

如果大家对这道题的坐标转换逻辑有疑问,也可以在这里一起讨论 🙂
另外,看到你定义的数组大小和循环边界有一点点小出入,在处理不同规模的数据时,记得也要留意一下这些细节。

已经写得很棒了,期待以后能看到你更多的解题思路分享~
0