题解

26 条题解

  • 7
    @ 2016-07-21 19:45:10

    过不了的人试试这组数据
    30 5 3
    2
    7
    17
    27
    29
    答案是7
    (这题真tm坑,用noip数据全过,用vijos数据就只有60分)

  • 4
    @ 2017-07-26 21:44:45

    水题水题
    NOIP2015Day2T1
    这题一看就是二分答案:
    1. 由于以最少的间距为自变量,需要拿掉的石头具有单调性,所以可以二分答案
    2. 对于当前答案,我们可以贪心的来
    3. 对于终点的特殊情况其实不特殊:如果终点要被拿掉,那么其实就是把终点前面那个拿掉
    时间复杂度: O(n log L)
    空间复杂度: O(n)

    过路人,贴代码<1A><用时6分钟>

    #include <cstring>
    #include <algorithm>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    using namespace std;
    const int N=5e4+5,MaxL=1e9;
    int n,m,L;
    int dis[N];
    int check(int d){
        int cnt=0,pos=0;
        for (int i=1;i<=n+1;i++)
            if (dis[i]-pos<d)
                cnt++;
            else
                pos=dis[i];
        return cnt;
    }
    int main(){
        scanf("%d%d%d",&L,&n,&m);
        for (int i=1;i<=n;scanf("%d",&dis[i]),i++);//专业压行 
        dis[n+1]=L;
        int ans=0,le=1,ri=MaxL,mid,need;
        while (le<=ri){
            mid=(le+ri)>>1;//等效于mid=(le+ri)/2
            need=check(mid);
            if (need<=m)
                le=mid+1,ans=mid;
            else
                ri=mid-1;
        }
        printf("%d",ans);
        return 0;
    }
    
    • @ 2017-11-06 20:07:21

      我感觉我智商不够用了,这题都可以炸

  • 3
    @ 2016-11-16 20:16:45

    我发现凡是想不出来的题 就尝试二分答案
    比如借教室,思想和这题惊人相似
    思路:
    二分最大的距离(答案)
    看看符不符合要求
    因为第一个石头不能动
    所以如果第一个石头与第二个石头之间距离不符合要求
    那么必须拿走第二个石头
    以此类推 依次访问后面的石头
    如果 某块石头与前一个石头的距离小了
    我们有两个选择:拿走这个 或 拿走前一个
    然而此时 拿走前一个可以增大当前这个不足的距离
    但对前面的石头并无好处 因为前面的已经符合要求了
    所以选择移动后一块石头 还可能对后面有好处
    #include <cstdio>

    int main(){
    int lenth,n,m,p[50010];
    scanf("%d%d%d",&lenth,&n,&m);
    p[0]=0,p[n+1]=lenth;
    for(int i=1;i<=n;i++)
    scanf("%d",&p[i]);
    int l=1,r=lenth,mid,last,move,ans;
    while(l<=r){
    mid=(l+r)/2;
    last=0,move=0;
    for(int i=1;i<=n;i++){
    if(p[i]-p[last]<mid)
    move++;
    else
    last=i;
    }
    if(p[n+1]-p[last]<mid)
    move++;
    if(move>m)
    r=mid-1;
    else{
    ans=mid;
    l=mid+1;
    }

    }
    printf("%d",ans);
    return 0;
    }

  • 2
    @ 2016-07-17 20:54:52

    var
    a:array [0..100005] of longint;
    v,n,p,i,l,r,m,u,s:longint;
    begin
    read(v,n,p);
    for i:=1 to n do read(a[i]);
    a[0]:=0; a[n+1]:=v; inc(n);
    l:=1; r:=v;
    while (l<r) do begin
    m:=(l+r+1) div 2;
    s:=a[0]; u:=0;
    for i:=1 to n do
    if (a[i]-s>=m) then s:=a[i] else inc(u);
    if (u>p) then r:=m-1 else l:=m;
    end;
    write(l);
    end.

  • 1
    @ 2018-08-20 09:14:12

    简单二分

    #include<iostream>
    using namespace std;
    int L,n,m;
    int a[50002];
    
    int p(int x)
    {
        int p=0,q=0;
        for(int i=1;i<=n;i++)
        if(a[i]-p<x)    q++;
        else p=a[i];
        return q;
    }
    
    int main()
    {
        cin>>L>>n>>m;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        a[++n]=L;
        int l=0,r=L;
        int ans=-111;
        while(l<=r)
        {
            int mid=(l+r)/2;
            int x=p(mid);
            if(x<=m)
            l=mid+1,ans=mid;
            else
            r=mid-1;
        }
        cout<<ans;
        return 0;
    }
    
  • 1
    @ 2018-02-13 12:15:17
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <set>
    #include <limits>
    #include <string>
    #include <sstream>
    #include <thread>
    using namespace std;
    
    const int oo_min=0xc0c0c0c0,oo_max=0x3f3f3f3f;
    
    namespace dts
    {
        typedef long long ll;
        
        ll n,m,l;
        ll a[50000+1];
        
        ll check(ll v)
        {
            ll pos=a[0],ans=0;
            for (ll i=1;i<=n;i++)
                if (a[i]-pos<v)
                    ans++;
                else
                    pos=a[i];
            return ans;
        }
        
        ll work()
        {
            ll left,right;
            for (left=0,right=l;right-left>1;)
            {
                ll mid=(left+right)/2;
                if (check(mid)<=m)
                    left=mid;
                else
                    right=mid;
            }
            if (check(right)<=m)
                return right;
            else
                return left;
        }
        
        void main()
        {
            while (~scanf("%lld%lld%lld",&l,&n,&m))
            {
                a[0]=0;
                for (ll i=1;i<=n;i++)
                    scanf("%lld",&a[i]);
                a[++n]=l;
                printf("%lld\n",work());
            }
        }
    };
    
    int main()
    {
        dts::main();
    }
    
  • 1
    @ 2017-10-23 17:00:58
    #include <iostream>
    #include <iomanip>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <algorithm>
    #include <cctype>
    #include <vector>
    #include <queue>
    using namespace std;
    int a[50001],b[50001];
    int k,n,m,x,l,r,mid,ans;
    bool check(int mid)
    {
        int s=0;
        int ss=0;
        for(int j=0;j<=n;j++)
        {
            ss+=b[j];
            if(ss<mid)
            {
                s++;
            }
            else
            {
                ss=0;
            }
        }
        if(s>m)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    int main()
    {
        scanf("%d%d%d",&k,&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=0;i<n;i++)
        {
            b[i]=a[i+1]-a[i];
        }
        b[n]=k-a[n];
        l=0;
        r=1000000000;
        while(l<r)
        {
            mid=(l+r)>>1;
            if(check(mid)==true)
            {
                ans=mid;
                l=mid+1;
            }
            else
            {
                r=mid;
            }
        }
        printf("%d",ans);
        return 0;
    }
    
  • 0
    @ 2017-07-17 18:54:37

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int main(){
    //freopen("2015stone.in","r",stdin);
    //freopen("2015stone.out","w",stdout);
    int l,n,m;
    int a[50002],cnt,x,y,mid,last,flag,ans;
    scanf("%d%d%d",&l,&n,&m);
    a[0]=0;
    a[n+1]=l;
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    x=0;
    y=l;
    while(x<=y){
    flag=1;
    cnt=0;
    last=0;
    mid=x+(y-x)/2;
    for(int i=1;i<=n+1;i++){
    if(a[i]-last<mid)
    cnt++;
    else
    last=a[i];
    if(cnt>m){
    flag=0;
    break;
    }
    }
    if(flag){x=mid+1;ans=mid;}else y=mid-1;
    }
    printf("%d",ans);
    }

  • 0
    @ 2016-12-30 16:43:50
    #include<cstdio>
    #define reg register
    const int maxn=50001;
    int len,m,n,mid;
    int dis[maxn];
    inline int check(int l,int r)
    {
        mid=(l+r)>>1;
        reg int num=0,last=0;
        for(reg int i=1;i<=n+1;i++)
        {
            if(dis[i]-last<mid)
                num++;
            else
                last=dis[i];
        }
        if(num>m)
            return 0;
        else
            return 1;
    }
    int main()
    {
        scanf("%d%d%d",&len,&n,&m);
        for(reg int i=1;i<=n;i++)
            scanf("%d",&dis[i]);
        dis[n+1]=len;
        int l=1,r=len,ans;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(check(l,r))
            {
                ans=mid;
                l=mid+1; 
            }
            else
                r=mid-1;
        }
        return !printf("%d\n",ans);
    }
    
  • 0
    @ 2016-12-30 16:43:34

    #include<cstdio>
    #define reg register
    const int maxn=50001;
    int len,m,n,mid;
    int dis[maxn];
    inline int check(int l,int r)
    {
    mid=(l+r)>>1;
    reg int num=0,last=0;
    for(reg int i=1;i<=n+1;i++)
    {
    if(dis[i]-last<mid)
    num++;
    else
    last=dis[i];
    }
    if(num>m)
    return 0;
    else
    return 1;
    }
    int main()
    {
    scanf("%d%d%d",&len,&n,&m);
    for(reg int i=1;i<=n;i++)
    scanf("%d",&dis[i]);
    dis[n+1]=len;
    int l=1,r=len,ans;
    while(l<=r)
    {
    mid=(l+r)>>1;
    if(check(l,r))
    {
    ans=mid;
    l=mid+1;
    }
    else
    r=mid-1;
    }
    return !printf("%d\n",ans);
    }

  • 0
    @ 2016-11-18 08:19:15

    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int M = 50005;

    int d[M], len, n, m;

    bool check(int x){
    int past = 0, tot = 0;
    for(int i = 1; i <= n + 1; i++)
    if(d[i] - past < x)
    tot++;
    else
    past = d[i];
    return tot <= m;
    }

    int main()
    {
    scanf("%d%d%d", &len, &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &d[i]);
    d[n+1] = len;
    int l = 1, r = len, ans;
    while(l <= r){
    int mid = l + r >> 1;
    if(check(mid))
    ans = mid, l = mid + 1;
    else
    r = mid - 1;
    }
    printf("%d", ans);
    return 0;
    }

  • 0
    @ 2016-11-15 19:08:09

    二分法
    const maxn=50009;
    var a:array[0..maxn]of longint;
    i,l,n,m,left,right,mid:longint;
    function tri(mid:longint):boolean;
    var count,pre,next:longint;
    f:array[0..maxn]of boolean;
    begin
    tri:=false;
    fillchar(f,sizeof(f),true);
    i:=0;next:=1;count:=0;
    while next<=n do
    begin
    while (a[next]-a[i]<mid)and(next<=n) do
    begin
    f[next]:=false;
    inc(next);
    inc(count);
    end;
    i:=next;next:=i+1;
    end;
    i:=n;
    while not f[i] do
    dec(i);
    if a[n+1]-a[i]<mid then inc(count);
    if count<=m then tri:=true;
    end;
    begin
    assign(input,'b.txt');reset(input);
    readln(l,n,m);
    for i:=1 to n do
    readln(a[i]);
    a[0]:=0;a[n+1]:=l;
    left:=0;
    right:=l;
    while left+1<right do
    begin
    mid:=(left+right)div 2;
    if not tri(mid) then right:=mid
    else left:=mid;
    end;
    writeln(left);close(input);
    end.

  • 0
    @ 2016-11-02 16:54:08

    同过noip数据过不了vijos数据,vijos数据真心良心。

  • 0
    @ 2016-08-31 20:24:37

    嗯,我决定精简代码,去掉读入优化......
    ```
    #include <bits/stdc++.h>
    using namespace std;
    int L, N, M;
    int s[50005];

    int main() {
    scanf("%d%d%d",&L,&N,&M);
    s[0] = 0;
    for(int i=1; i<=N; i++) scanf("%d", &s[i]);
    s[N+1] = L;
    int l = 1, r = L;
    while(l <= r) {
    int mid = (l + r) >> 1;
    int m = 0, pre = 0;
    for(int i=1; i<=(N+1); i++)
    if(s[i] - s[pre] < mid) m++;
    else pre = i;
    if(m <= M) l = mid+1;
    else r = mid-1;
    }
    printf("%d\n", r);
    return 0;
    }
    ```

  • 0
    @ 2016-08-31 20:22:49

    二分答案,O(n)判断解。
    总复杂度O(nlogn)。
    ```cpp
    #include <bits/stdc++.h>
    using namespace std;
    inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
    }
    int L, N, M;
    int s[50005];

    int main() {
    L=read(); N=read(); M=read();
    s[0] = 0;
    for(int i=1; i<=N; i++) s[i] = read();
    s[N+1] = L;
    int l = 1, r = L;
    while(l <= r) {
    int mid = (l + r) >> 1;
    int m = 0, pre = 0;
    for(int i=1; i<=(N+1); i++)
    if(s[i] - s[pre] < mid) m++;
    else pre = i;
    if(m <= M) l = mid+1;
    else r = mid-1;
    }
    printf("%d\n", r);
    return 0;
    }
    ```

  • 0
    @ 2016-08-29 10:49:08

    先反向判断到最后一个不用拿走的点,再正向判断
    c++
    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <cmath>
    #include <cstdlib>
    #include <algorithm>
    using namespace std;
    int i,j,m,n,l,p,q,dis[50002],disn,movd;
    bool can(int mid)
    {
    i=n;
    while(l-dis[i]<mid)
    {
    i--;
    movd++;
    }
    int end=i;
    int st=0;
    for(i=1;i<=end;i++)
    {
    if(dis[i]-st<mid)movd++;
    else st=dis[i];
    }
    if(movd<=m)return true;
    return false;
    }
    int main()
    {
    scanf("%d%d%d",&l,&n,&m);
    for(i=1;i<=n;i++)
    {
    scanf("%d",&dis[i]);
    }
    int le=1;int ri=l;
    while(le<ri)
    {
    int mid=(ri+le+1)/2;
    movd=0;
    if(can(mid))le=mid;
    else ri=mid-1;
    }
    cout<<le;
    }

  • 0
    @ 2016-07-13 15:59:46

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <climits>
    using namespace std;

    #define MAXN 50005
    #define MAXM 50005
    int L, N, M;
    int D[MAXN];
    int Ans;

    bool Check(const int &dist)
    {
    int cnt = 0;
    int LastPos = 0;
    for(int i = 1; i <= N+1; i++)
    {
    if(D[i]-LastPos < dist) cnt++;
    else LastPos = D[i];
    if(cnt > M) return 0;
    }
    return 1;
    }

    int main()
    {
    cin >> L >> N >> M;
    int l = INT_MAX;
    int r = L/(N-M);
    for(int i = 1; i <= N; i++)
    {
    scanf("%d", D+i);
    }
    sort(D+1, D+N+1);
    D[N+1] = L;
    //for(int i = 1; i <= N+1; i++)cout<<D[i]<<' ';
    // cout<<endl;
    for(int i = 1; i <= N+1; i++) l = min(l, D[i]-D[i-1]);
    while(1)
    {
    //cout<<l<<' '<<r<<endl;
    int div = l + r >> 1;
    if(Check(div)) l = div;
    else r = div;
    if(l+1 == r )
    {
    Ans = l;
    if(Check(r)) Ans = r;
    break;
    }
    }
    cout << Ans << endl;
    return 0;
    }

  • 0
    @ 2016-06-11 19:37:19

    唉,经典的二分,边界要好好处理一下,不然会炸。
    不过noip的数据竟然可以骗边界……
    ```c++
    #include<cstdio>
    #include<cstring>
    #include<vector>
    using namespace std;

    vector<int> stones;
    int l,n,m;
    int s=2e9,b;

    bool is_ok(int x)
    {
    int flag=0;
    int remove=0;
    for(int i=0;i<=n;i++)
    {
    flag=i;
    for(int j=i+1;j<=n;j++)
    {
    if(stones[j]-stones[i]>=x) {i=j-1;break;}
    remove++;
    if(j==n) {i=j;}
    }
    }
    if(flag&&l-stones[flag]<x) remove++;
    return remove<=m;
    }

    int main()
    {
    /*freopen("in","r",stdin);*/
    scanf("%d%d%d",&l,&n,&m);
    stones.push_back(0);
    for(int i=1;i<=n;i++)
    {
    int k;
    scanf("%d",&k);
    s = min(k-stones[i-1],s);
    stones.push_back(k);
    }
    s = min(l-stones[stones.size()-1],s);
    b = l;
    while(s<b)
    {
    int middle=s+(b-s+1)/2;
    if(is_ok(middle)) s=middle;
    else b=middle-1;
    }

    printf("%d\n",s);
    return 0;
    }
    ```

  • 0
    @ 2016-05-31 19:11:18
    #include<cstdio>
    #include<cmath>
    int d[51000],L,N,M;
    int pd(int m)
    {
        int ans=0;
        int l=1,r=N,t;
        while(d[l]-0<m&&l<=r)l++,ans++;
        while(L-d[r]<m&&r>=l)r--,ans++;
        while(l<r)
        {
            for(t=l+1;d[t]-d[l]<m;t++)
            {
                ans++;
                if(t+1>r)return ans;
            }
            l=t;
        }
        return ans;
    }
    int main()
    {
        scanf("%d%d%d",&L,&N,&M);
        for(int i=1;i<=N;i++)
            scanf("%d",&d[i]);
        int l,r,m;
        l=0;
        r=1000000000;
        while(l<r)
        {
            m=ceil((l+r)/2.0);
            if(pd(m)<=M)
                l=m;
            else r=m-1;
        }
        printf("%d",l);
        return 0;
    }
    
  • 0
    @ 2015-11-23 20:24:22

    #include<stdio.h>
    int line[55555]={0};
    int m,n;
    int ok(int a)
    {
    int i,head=0,count=0;
    for(i=1;i<=n;i++)
    {
    if(line[i]-head<a) count++;
    else head=line[i];
    }
    if(count<=m) return 1;
    else return 0;
    }
    int main()
    {
    int i,j,s,ans,head,tail,count=0;
    scanf("%d%d%d",&s,&n,&m);
    for(i=1;i<=n;i++)
    scanf("%d",&line[i]);
    line[n+1]=s;

    head=1;tail=s;
    while(head<=tail)
    {
    if(ok((head+tail)/2)==1)
    head=(head+tail)/2+1;
    else tail=(head+tail)/2-1;
    ans=(head+tail)/2;
    }
    printf("%d",ans);
    return 0;
    }
    C的,用noi数据100分
    用vijos60分.....简直了。。【接招吧】,南小鸟精神污染!!!!

信息

ID
1981
难度
6
分类
(无)
标签
递交数
4199
已通过
1015
通过率
24%
被复制
9
上传者