明天就比赛了,求大佬帮看谢谢!

回复帖子

@tan_gent 2018-11-09 10:30 回复

跳房子

为什么第一个样例我会输出1?

#include <bits/stdc++.h>
using namespace std;

int n,d,k,x[500009],s[500009],f[500009];
int l,r=2147483646,mid,ans;
long long summ;
bool zhazhi(int g) {
    memset(f,0,sizeof(f));
    if(g<d) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<i; j++) {
                if(x[i]-x[j]>=d-g&&x[i]-x[j]<=d+g) {
                    f[i]=max(f[i],f[j]+s[i]);
                }
            }
        }
        return f[n]>=k;
    } else {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<i; j++) {
                if(x[i]-x[j]<=d+g) {
                    f[i]=max(f[i],f[j]+s[i]);
                }
            }
        }
        return f[n]>=k;
    }
}
int main() {
    scanf("%d %d %d",&n,&d,&k);
    for(int i=1; i<=n; i++) {
        scanf("%d %d",&x[i],&s[i]);
        summ+=s[i];
    }
    if(summ<k) {
        printf("-1");
        return 0;
    }
    while(l<r) {
        mid=(l+r)/2;
        if(zhazhi(mid)==1) {
            r=mid;
            ans=r;
        } else {
            l=mid+1;
        }
    }
    printf("%d",ans);
    return 0;
}
@tan_gent 2018-11-09 10:33 回复

啊啊啊!我真的想知道啊啊啊!

@tan_gent 2018-11-09 10:34 回复

哦哦哦我懂了! 有个||我打成了&&。。。。。