(luogu2678)跳石头(NOIP2015D2T1)

发表于 | 分类于 ，

经典二分题

题目描述:

略

思路:

二分+贪心判断

查找最大值考虑二分答案

对于某一个长度, 枚举每块石头, 如果这个石头与前一个石头的距离小于查找的距离, 则移除这块石头, 否则留下. 当移除石头的数量小于等于m时该长度合法

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstdio>
using namespace std;
const int Mn(50005);
int n,m;
int dis[Mn];
bool chk(int d) //判断函数
{
    int nos(0),lst(0); //搬走的石头数和上块未搬走的石头位置
    for(int i(1);i<=n+1;++i)
    {
        if(dis[i]-dis[lst]<d)   ++nos;
        else    lst = i;
    }
    return nos<=m;
}
int main()
{
    int len;
    cin >> len >> n >> m;
    dis[n+1] = len; //终点石头距起点len
    for(int i(1);i<=n;++i)
        scanf("%d",dis+i);
    int l(0),r(len);
    while(l<=r) //二分答案
    {
        int mid((l+r)>>1);
        if(chk(mid))    l=mid+1;
        else    r=mid-1;
    }
    cout << r;
    return 0;
}