自动搬运

查看原文

来自洛谷，原作者为

	greenheadstrange 这个家伙很菜，什么也没有留下

搬运于2025-08-24 21:26:49，当前版本为作者最后更新于2019-06-10 16:06:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

贪心大法好啊好，不卡常，不超时，简单代码就AC。

言归正传，首先将每条线段按照起始端点进行从小到大的排序。然后在一个for循环搜一遍。

时间复杂度O（nlogn）

废话少说，直接上代码：

#include<bits/stdc++.h>
using namespace std;
struct note{
	int l,r;
}a[10005];//定义结构体
int n,m,ans;
bool cmp(const note&aa,const note&bb){
	return aa.l<bb.l;
}//按照始端点从小到大排序
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r);
	sort(a+1,a+n+1,cmp);
	int x=0;//x表示当前的木板铺到了哪里
	for(int i=1;i<=n;i++){
		x=max(x,a[i].l);//如果x小于当前泥泞路的始端点
		while(x<a[i].r){
			x+=m;//加上木板长度
			ans++;//答案总数加1
		}
	}
	printf("%d",ans);
	return 0;
}

结束语：OI路上困难重重，唯有静下来，才能成为顶尖高手