NOIP2015提高组跳石头 ACM-ICPC2017香港 E（选择/移除+二分答案）

跳石头

题目背景

一年一度的“跳石头”比赛又要开始了!

题目描述

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走

输入输出格式

输入格式：

第一行包含三个整数

接下来 $D_i( 0 < D_i < L)Di(0<Di<L)，表示第 ii 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。$

输出格式：

一个整数，即最短跳跃距离的最大值。

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

输入输出样例 1 说明：将与起点距离为

另：对于 $20\%20%的数据,0 ≤ M ≤ N ≤ 100≤M≤N≤10。$

对于 $50\%50%的数据,0 ≤ M ≤ N ≤ 1000≤M≤N≤100。$

对于 $100\%100%的数据,0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,0000≤M≤N≤50,000,1≤L≤1,000,000,000。$

#include<bits/stdc++.h>
#define MAX 50005
using namespace std;
typedef long long ll;

int a[MAX];

int main()
{
    int t,i,j;
    int L,N,M;
    scanf("%d%d%d",&L,&N,&M);
    a[0]=0;
    for(i=1;i<=N;i++){
        scanf("%d",&a[i]);
    }
    a[N+1]=L;
    int l=0,r=1000000000,m;
    int ans=0;
    while(l<=r){
        m=(l+r)/2;
        int pre=0,cnt=1;
        for(i=1;i<=N+1;i++){
            if(a[i]-a[pre]>=m){
                pre=i;
                cnt++;
            }
            
        }
        if(cnt>=N+2-M){
            ans=max(ans,m);
            l=m+1;
        }
        else{
            r=m-1;
        }
    }
    printf("%d
",ans);
    return 0;
}

跳石头（移除）

61.05%
2000ms
262144K

$P_1, P_2, ... , PL (0 le Pi le 1, 000, 000)P1,P2,...,PL(0≤Pi≤1,000,000) and the company wants to install SS base stations at the LL candidate locations. What is the largest minimum distance among the SS base stations?$

Input

The input data includes multiple test sets.

Each set starts with a line which specifies $P_1P1 , P_2P2 , ... , P_LPL . The input data ends “00 00”.$

Output

For each set, you need to output a single line which should be the largest minimum distance among the base stations.

For the first set, the

样例输入

样例输出

4
3

题目来源

ACM-ICPC 2017 Asia HongKong

#include<bits/stdc++.h>
#define MAX 100005
using namespace std;
typedef long long ll;

int a[MAX];

int main()
{
    int t,i,j;
    int n,s;
    while(scanf("%d%d",&n,&s)&&n+s){
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        sort(a+1,a+n+1);
        int l=0,r=1000000,m;
        int ans=0;
        while(l<=r){
            m=(l+r)/2;
            int pre=1,cnt=1;
            for(i=2;i<=n;i++){
                if(a[i]-a[pre]>=m){
                    pre=i;
                    cnt++;
                }
                
            }
            if(cnt>=s){
                ans=max(ans,m);
                l=m+1;
            }
            else{
                r=m-1;
            }
        }
        printf("%d
",ans);
    }
    return 0;
}

E（选择）

NOIP2015提高组 跳石头 ACM-ICPC2017香港 E（选择/移除+二分答案）

跳石头