抓娃娃

题目 抓娃娃

思路分析

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

//还有1h45m 把剩余题都看一下 估计只能干出一道来了

//这题 好像能写 但是第九题貌似能骗 先写第九题

//9写了 10跳了 还有1h13m

//暴力肯定能做 但想找一下优化的点

//先是n条线段 再是m条查询区间

//问这m条区间分别框住了多少个线段（达到一半就算框住）

//直接先想暴力吧

/*

如何判断某个区间被框住

	区间首先全都按左端点排序

	大概分为以下几种情况

	sl---sr  中点sm shl

	ql-----qr

	若ql小于等于sl 则只有qr>=sm时 才能包含

	若ql大于等于sl 且 小于等于 sm时 则只有  qr>=ql+shl才能包含

	若ql大于 sm 则直接不可能

	所以对于每条线段 要存储它的 左端点 中点 以及一半长度 即sl,sm,shl

	而对于每个区间 只需要存左端和右端即可

*/

typedef pair<double,double> PDD;

struct seg{

	double sl;

	double sm;

	double shl;

	bool operator<(const seg& other)const{

		return sl<other.sl;

	}

};

vector<seg> segs;

vector<PDD> query;

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n,m; cin>>n>>m;

	for(int i=0;i<n;i++){

		double l,r;cin>>l>>r;

		double sl=l,sm=(l+r)*1.0/2,shl=(r-l)*1.0/2;

		segs.push_back({sl,sm,shl});

	}

	sort(segs.begin(),segs.end());

//	for(auto x:segs) cout<<x.sl<<" "<<x.sm<<" "<<x.shl<<endl;

	for(int i=0;i<m;i++){

		double l,r;cin>>l>>r;

		query.push_back({l,r});

	}

//	for(auto x:query)	cout<<x.first<<" "<<x.second<<endl;

	for(auto q:query){

		auto ql=q.first,qr=q.second;

		int cnt=0;

		for(auto s:segs){

			auto sl=s.sl,sm=s.sm,shl=s.shl;

			if(ql<=sl && qr<sm)	continue;

			if(ql>=sl && ql<=sm && qr<ql+shl) 	continue;

			if(ql>sm)	continue;

			cnt++;

		}

		cout<<cnt<<endl;

	}

	return 0;

}

同类题型

视频讲解

⬅️ AB路线 🏠 00-冲刺国赛 ➡️ 拼数字