当前位置:编程学习 > C/C++ >>

poj-3258-River Hopscotch-二分

题意:
一条河长度为 L,河的起点(Start)和终点(End)分别有2块石头,S到E的距离就是L。
河中有n块石;
输入的每块石头的距离是到起点的距离。
问现在要移除m块石头(S和E除外),每次移除的是与当前最短距离相关联的石头,要求移除m块石头后,使得那时的最短距离尽可能大,输出那个最短距离。
做法:
和上一道题目的做法是一样的都是二分。
[html]  
#include<iostream>  
#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
using namespace std;  
int a[100100];  
int n,m;  
int sw(int mid)  
{  
    int s,num,i;  
    s=0;  
    num=0;  
    for(i=1;i<n+2;i++)  
    {  
        if((s=s+a[i]-a[i-1])<=mid)  
        {  
            num++;  
        }  
        else  
        {  
            s=0;  
        }  
    }  
    if(num>m)return 0;  
    else return 1;  
}  
int main()  
{  
    int l,r,i,mid,end;  
    cin>>end>>n>>m;  
    r=end;  
    l=end;  
    a[0]=0;  
    a[n+1]=end;  
    for(i=1;i<=n+1;i++)  
    {  www.zzzyk.com
        if(i<n+1)  
        scanf("%d",&a[i]);  
        if(l>a[i]-a[i-1])l=a[i]-a[i-1];  
    }  
    mid=(l+r)/2;  
    sort(a,a+(n+2));  
    while(l<=r)  
    {  
        if(sw(mid))l=mid+1;  
        else r=mid-1;  
        mid=(l+r)/2;  
    }  
    cout<<l<<endl;  
    return 0;  
}  
 
补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,