首页 > 代码库 > 南阳nyoj586疯牛 和nyoj619详解总结

南阳nyoj586疯牛 和nyoj619详解总结

这里先看nyoj619青蛙过桥,这样便于理解这两道题的共同点:最大值中的最小值

题意:有一条河长L,中间有 n 块石头,青蛙最多可以跳 m 次,问题是:要保证青蛙能跳过去,那么它至少能一下跳多远,才能在m次范围内跳过去;

最大值中的最小值:这里要保证m次能跳过去,那么在这个过程中就会有很多种方法能在m次之内跳过去,那么,每一个方法中,我们就会有一个最大的跳跃距离!

比如:L=20,n=1;m=2;石头的位置是5

那么方法有:1.一次就跳过去,2.借助中间的石头,两次跳过去;那么在方法一中的最大的距离就是20,在第二种方法中,最大的距离就是15,那么方法二中的最大值15就是所有最大值中的最小的一个,也就是保证青蛙跳过去的至少能跳的距离


解决:这里要用到二分加贪心

二分时候,区间(l,r),l是石头两两之间最大的距离,r是L河宽,mid=(l+r)/2作为每次应该跳跃的距离,然后二分贪心;

贪心过程中,对于二分中的每一个mid的值,我们贪心求出以这个距离跳跃,能多少次跳过河!

上马,代码中注释:

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 500005

int L,n,m;
int stone[MAX];

int jump(int x)
{
    int cnt = 1;
    int sum = 0;//青蛙每次的起跳点,初始为0
    for(int i = 0; i <= n; i ++)
    {
        if(stone[i] - sum == x )//如果这个石头到sum这点的距离刚好是x,那么刚好能跳过,sum更新为这个石头坐标
        {
            cnt ++;
            sum = stone[i];
        }
        else if(stone[i] - sum > x)//青蛙不能从sum跳到stone,那么,sum就更新为前面那个石头的坐标
        {
            cnt ++;
            sum = stone[i-1];
        }
    }
    return cnt;
}

int main()
{
    while(cin>>L>>n>>m)
    {
        for(int i = 0; i < n; i ++) cin>>stone[i];
        sort(stone,stone+n);
        stone[n] = L; //把河的宽度加入

        int l,r;
        r = L;
        l = 0;
        for(int i = 1; i <= n; i ++)//找二分区间的左值
        {
            if(stone[i] - stone[i-1] > l) l = stone[i]-stone[i-1];
        }

        int mid;
        while(l <= r)
        {
            mid = (l+r)/2;
            if(jump(mid) <= m) r = mid-1;
            else l = mid+1;
        }
        cout <<l<<endl;
    }
    return 0;
}

nyoj586疯牛

这里和上面只有一点点区别:

第一:二分区间的左右值(0,cow[n-1]-cow[0]);(排好序之后的);

第二:青蛙那题是跳的次数,而这里是安排的牛数,就像线段上的点的关系一样,一个线段,两个端点,类似于青蛙要跳一次,但是可以安排两头牛在两个端点上,那么这里二分的时候,判断就应该是 <= c-1;  而不是青蛙那里的 <=m

第三就是贪心过程中,不要区分 == x 和 > x的情况

具体看代码:

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 100005

int n,c;
int cow[MAX];

int din(int x)
{
    int cnt = 1;
    int sum = cow[0];
    for(int i = 1; i < n; i ++)
    {
        if(cow[i] - sum >= x) //不要区分,满足就把牛放在这点,sum更新为此点坐标,应为青蛙那不能跳过来,就是前面一点
        {
            cnt ++;
            sum = cow[i];
        }
    }
    return cnt;
}

int main()
{
    while(cin>>n>>c)
    {
        for(int i = 0; i < n; i ++) cin >> cow[i];
        sort(cow,cow+n);

        int l = 0;
        int r = cow[n-1]-cow[0];

        int mid;
        while(l <= r)
        {
            mid = (l+r)/2;
            if(din(mid) <= c-1) r = mid-1;
            else l = mid+1;
        }
        cout<<l-1<<endl;
    }
    return 0;
}
个人愚昧观点,欢迎讨论与指正