中级光能
2775 泥泞的小路
题目描述 Description
暴雨过后的农场到镇上的公路上有一些泥泞路，给你若干块长度为L的木板，你可以用这些木板铺在泥泞的小路上，问至少需要多少块木板，才能把所有的泥泞路覆盖住。
输入描述 Input Description
第一行：两个正整数 n ( n ≤ 10000 ) 和 L ( L ≤ 10000 )，分别表示有n段泥泞的路，木板的长度为L
接下来n行：每一行两个整数 s 和 e ( s ≤ e ≤ 10^9 )，表示每一段泥泞路的起点和终点。
输出描述 Output Description
一个正整数，表示木板数。
样例输入 Sample Input
3 3
1 6
13 17
8 12
样例输出 Sample Output
5
（样例输出为什么是5？不应该是6吗？哪位大神给我讲讲思路。记住，是思路！！！谢谢！）
张舒斌在2018-10-02 19:18:07追加了内容
刚刚写完程序，悲催的是是错的。大佬们给我看一看啊~
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,l,count=0,len,c;
int s[100000],f[100000];
double ok;
cin>>n>>l;
for(int i=1;i<=n;i++)
{
cin>>s[i];
}
for(int i=1;i<=n;i++)
{
cin>>f[i];
}
for(int i=1;i<=n-1;i++)
{
for(int j=i+1;j<=n;j++)
{
if(s[i]>s[j])
{
swap(s[i],s[j]);
swap(f[i],f[j]);
}
}
}
for(int i=1;i<=n;i++)
{
len=f[i]-s[i];
ok=len;
if(len%l>s[i+1]-f[i])
{
c=len%i-s[i+1]-f[i];
ok=f[i+1]-s[i+1]-c;
count+=int(ok/l+0.5);
}
else
{
count+=int(ok/l+0.5);
}
}
cout<<count;
return 0;
}
变量count是计数有多少块板
len是泥泞路的长度
c是超过泥泞路，伸到下一块泥泞路的长度
修练者
画个图：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
* * * * * * * * * * * * * * * * * * * *
虽然有点丑，但大概可以理解了吧 . . . . . .
* 号代表泥泞路
1~6为一条路，8~12和13~17，也就是8~17是一条路
1~6要2块板 8~17要3块板 2+3=5块板
因此呢，用 a数组 存起始点，b数组 存终止点
sort(a+1,a+1+n);
sort(b+1,b+1+n);
用 s 存 a[1] , 也就是第一条路的起始点。
for(i=1; i<=n; i++) {
while(s<b[i]) { // 注意！不能用直接除的方法
s+=l;
k++;
}
s=max( s , a[i+1] ); //如果 j 的终止点能和下一条路的起始点接上，就接上去。
}
k为最优解
输出k
我是AC。
望采纳
高级光能
（6-1+17-13+12-8）/3=5
就是每一行第二个数减第一个数的和除以L
初级启示者
洛谷上搜一下，叫做"泥泞路"
赵逸凡在2018-10-04 22:36:37追加了内容
cin>>n>>l;
for(i=1;i<=n;i++)
cin>>s[i]>>e[i];
sort(s+1,s+1+n); sort(e+1,e+1+n);//这里把起点和终点排序（因为每次输入起点小于终点，所以排完序后不会出现起点比终点小的情况）；
d=s[1];//d存放起点；
for(i=1;i<=n;i++)
{
while(d<e[i])//当起点大于终点，不再执行（也可以避免了起点比终点大的尴尬）；
{
d+=l;
h++;//统计木板数
}
d=max(d,s[i+1]);//比较当前终点和下一个起点，选大的，避免重复；
}
cout<<h;//输出木板数；
这是核心
中级天翼
1
高级光能
你AC了吗？
代码发下
高级光能
6-1=5；
17-13=4；
12-8=4；
13/3=4；
4+1=5；
中级光能
有人回答吗？我没思路啊~
初级天翼
1
