POJ 3258 River Hopscotch(二分+贪心)

POJ 3258

题目大意

一条线段两个端点之间的距离是L,两端点之间分布着N个点，这N个点把线段分成了N+1份，现在让你最多去掉(第一次读错题想了很久不知道怎么做，remove是去掉不是移动，lll￢ω￢)M个点，问N+1份线段最小值的最大值是多少 (1≤L≤109,0≤M≤N≤50000) 。

分析

类似POJ 3273，也是用二分法来做
接下来的问题就是给定一个k，如何判断是否能够通过至多去掉M个点使得剩下线段的最小值大于等于k.
也是采用贪心的做法，从左到右扫描，遇见小于k的线段就把该线段右端去掉累加到下一段中继续比较。证明略。
需要注意的是最后一段需要单独处理。

代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;
int a[500005];
int len;
int n,m;
int maxa;//保存数组a中的最大值
bool Check(int k)//判断k是否满足要求
{
      int sum=0;
      int  x=0;
      for(int i=1;i<=n;i++)
      {
           if(sum+a[i]>=k){sum=0;}
           else {sum+=a[i];x++;}
      }
      if(sum+len-a[n]<k)x++;
      if(x<=m)return 1;
      else return 0;
}
void Work()
{
     int L=1;
     int R=len;
     int M;
     while(R>L)
     {
           M=(R+L+1)/2;
           if(Check(M)==1)L=M;
           else R=M-1;
     }
     cout<<L<<endl;
}
int main()
{
    while(~scanf("%d%d%d",&len,&n,&m))
    {
         for(int i=1;i<=n;i++){scanf("%d",&a[i]);}
         sort(a+1,a+1+n);
         for(int i=n;i>=1;i--)a[i]=a[i]-a[i-1];
         Work();
    }
    return 0;
}