贪心算法解题报告（D-Farmer John）

68 阅读 0 评论 45 点赞

我是靠谱客的博主犹豫哈密瓜，最近开发中收集的这篇文章主要介绍贪心算法解题报告（D-Farmer John），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：
Farmer John has a problem: the dirt road from his farm to town has suffered in the recent rainstorms and now contains (1 <= N <= 10,000) mud pools.

Farmer John has a collection of wooden planks of length L that he can use to bridge these mud pools. He can overlap planks and the ends do not need to be anchored on the ground. However, he must cover each pool completely.

Given the mud pools, help FJ figure out the minimum number of planks he needs in order to completely cover all the mud pools.
Input

Line 1: Two space-separated integers: N and L
Lines 2…N+1: Line i+1 contains two space-separated integers: s_i and e_i (0 <= s_i < e_i <= 1,000,000,000) that specify the start and end points of a mud pool along the road. The mud pools will not overlap. These numbers specify points, so a mud pool from 35 to 39 can be covered by a single board of length 4. Mud pools at (3,6) and (6,9) are not considered to overlap.
Output
Line 1: The miminum number of planks FJ needs to use.
Sample Input
3 3
1 6
13 17
8 12
Sample Output
5
HintINPUT DETAILS:

FJ needs to use planks of length 3 to cover 3 mud pools. The mud pools cover regions 1 to 6, 8 to 12, and 13 to 17.

OUTPUT DETAILS:

FJ can cover the mud pools with five planks of length 3 in the following way:
111222…333444555…

               .MMMMM..MMMM.MMMM....

               012345678901234567890

题义：
农民约翰想用几块等长的木板遮住他的农场，输入遮住距离有几段和木板的长度，和每段被遮住位置的起止位置，求出所用木板最少的数量。
思路：
定义一个结构体用来每一段的起止位置，定义一个函数，让每段根据起始时间从小到大排序，定义两个指针，记录每段的起止位置。在循环中计算每一段需要木板的数量，当每段距离的长度不恰好等于木板的倍数时，数量+1，更新末位置的指针，再与下一段的初位置进行比较，若大于下一段的初位置，则更新初位置的指针。
代码：

#include<iostream>
#include <stdio.h>
#include <cstring>
#include <iomanip>
#include <cmath>
#include <algorithm>
#define exp 1e-6
typedef long long ll;
using namespace std;
struct node
{
    int begin;
    int end;
} a[10010];
bool cmp(node a,node b)
{
    return a.begin<b.begin;

}
int main()
{
    int n,L,i,j;
    ios::sync_with_stdio(false);
    cin>>n>>L;
    for(i=0; i<n; i++)
        cin>>a[i].begin>>a[i].end;
    sort(a,a+n,cmp);
    int sum=0;
    int l=-1;
    for(i=0; i<n; i++)
    {
        if(l>=a[i].end)
            continue;
        if(l>a[i].begin)
        {
            int length=a[i].end-l;
            int num=length/L;
            if(length%L==0)
                num=num;
            if(length%L!=0)
                num++;
            l+=num*L;
            sum+=num;
        }
        else
        {
            int length=a[i].end-a[i].begin;
            int num=(length+L-1)/L;
            l=a[i].begin+num*L;
            sum+=num;
        }
    }
    cout<<sum<<endl;
    return 0;
}