自动搬运

查看原文

来自洛谷，原作者为

	翼德天尊 2019-09-26 ~ 2024-03-03

搬运于2025-08-24 21:43:03，当前版本为作者最后更新于2020-03-22 17:01:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

闲话不多说，不太懂这道题的同志们跟我来！跟着我逐步思考，让你秒懂此题！这题很水的

STEP 1 审题

经过整理，汇总改编抽象出一下条件：

1.有c条线段，已知它们的端点；

2.有l种点，已知它们的坐标以及每种点的个数；

3.问如果把那些点放入线段中，最多可以放进几个。

看吧，活脱脱的一个贪心中的线段覆盖问题！

STEP 2 规划做题方法

经过审（biao) 题 (qian)，我们了解了这是一道线段覆盖问题，那么，线段覆盖问题怎么做？

方法： 按右端点排序。

理由： 方便处理防晒霜摸到奶牛身上

但是，为什么不按左端点排序呢

证明： 现有三条线段，给出它们的左右端点（按左端点排序后）：

1 6 / / 2 3 / / 3 4

防晒霜两种（只给点的坐标，默认每种一瓶）（按大小排序后）：

3 / / 5

那么按正常的流程，“3”防晒霜给“1 6”线段，则5无法给另外两条线段，ans答案为1.

但如果按右端点排序，则结果为：

2 3 / / 3 4 / / 1 6

那么“3”防晒霜会给“2 3”线段使用，5会给“1 6”，从而有两个结果。

这个反例证明：右端点才能真正确定一条线段的位置

线段（奶牛）按右端点排序后，再从小到大将每个点（防晒霜）排序即可。

STEP 3: AC CODE 及 具体讲解

30行是不是很短（没有压行哦）

#include<bits/stdc++.h>//美丽可爱端庄大方的万能头
using namespace std;
int c,l,ans;//分别记录奶牛数量，防晒霜数量以及结果
struct node{//结构体储存方便排序
	int a,b;//两个数据
};
node cow[2501],fss[2501];//分别储存奶牛信息和防晒霜信息
int cmp(node x,node y){//排序1：给奶牛按右端点排序
	return x.b<y.b;
}
int cmp1(node x,node y){//排序2：给防晒霜按左端点排序
	return x.a<y.a;
}
int main(){
	scanf("%d%d",&c,&l);
	for (int i=1;i<=c;i++) scanf("%d%d",&cow[i].a,&cow[i].b);
	for (int i=1;i<=l;i++) scanf("%d%d",&fss[i].a,&fss[i].b);//正常输入输出
	sort(cow+1,cow+c+1,cmp);//奶牛排序
	sort(fss+1,fss+l+1,cmp1);//防晒霜排序
	for (int i=1;i<=c;i++){
		for (int j=1;j<=l;j++){//循环判断
			if (fss[j].b>0&&fss[j].a>=cow[i].a&&fss[j].a<=cow[i].b){//判断是否符合点在线段内且该点还有剩余
				fss[j].b--,ans++;//减去一个相应点，答案+1
				break;//找到合适点选，就换另一个线段
			}
		}
	}
	printf("%d\n",ans);//正常输出
	return 0;//据说有好习惯会被人点赞哦，不知道是不是真的
} 

STEP 4 完结撒花

恭祝各位RP++，有还是不懂的就在评论区留言吧，我会回复的。懂了的大佬们，你看蒟蒻这么辛苦的敲字，点个赞鼓励一下吧！