AcWing 782. 这题是不是有问题啊==    原题链接    中等

作者： 作者的头像   脆脆鲨 ,  2019-05-15 15:30:47 ,  所有人可见 ,  阅读 892

0


对于
4 3
1 1
2 100
3 100
4 1
这组用例，应该是1+1=2吧，如果按照答案输出是100。
下面是我的代码，主要看helper里面的while，应该要先移动right直到right-left>=d才行吧，这样才能保证有两个银行可以偷，如果按照yxc的思路，在一开始会用上靠前的一个比较大的数据，比如上面用例的2 100，而后面2 100这个数据根本不会被用到。
如果我说的不对，真心希望有人指正，这题搞了我3个小时了……

import java.util.*;
class Main{
    static class Bank{
        int location;
        int money;
        public Bank(int location,int money){this.location=location;this.money=money;}
        public String toString(){return "location:"+location+"  money:"+money;}
    }

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int d=scanner.nextInt();
        Bank[] banks=new Bank[n];
        for(int i=0;i<n;i++){
            banks[i]=new Bank(scanner.nextInt(),scanner.nextInt());
        }
        //Arrays.sort(banks, Comparator.comparing(Bank -> Bank.location));
        Arrays.sort(banks,new Comparator<Bank>(){
            public int compare(Bank a,Bank b){
                return a.location-b.location;
            }
        });
        for(Bank b:banks){
            //System.out.println(b);
        }
        System.out.println(helper(banks,n,d));
    }

    private static int helper(Bank[] banks,int n,int d){
        int ans=0;
        int preMax=banks[0].money;
        int left=0,right=0;
        while(right<n){
            //先移动right，是的right-left>=d
            while(right<n && banks[right].location-banks[left].location<d) right++;
            if(right<n){
                //如果此时right没有越界，就更新一下ans
                ans=Math.max(ans,preMax+banks[right].money);
            }
            //接着移动left，直到right-left<d
            while(right<n && left<right && banks[right].location-banks[left].location>=d){
                left++;
                preMax=Math.max(preMax,banks[left].money);
            }
        }
        return ans;
    }
}

2 评论

用户头像
acw_lyl   2020-03-13 16:25         踩      回复 
int main(){
    int n,d;
    cin>>n>>d;
    for(int i=0;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        val[i]={a,b};
    }

    sort(val,val+n);

    int ans=0;
    int max_v=val[0].second;
    for(int i=1,j=0;i<n;i++)
    {
        while(j+1<i&&val[i].first-val[j+1].first>=d)
        {
            j++;
            max_v=max(max_v,val[j].second);
        }

       if(val[i].first-val[j].first>=d) ans=max(ans,val[i].second+max_v);
    }

    cout<<ans;
    return 0;
}
用户头像
熊本熊本熊   2019-05-17 16:53         踩      回复

在这一段里，你的这句话没有必要：

while(right<n){
    //先移动right，是的right-left>=d
    while(right<n && banks[right].location-banks[left].location<d) right++;
// 下面这个if语句没有必要，和更下面的那个while功能重复了，删了也不会影响逻辑
    if(right<n){
        //如果此时right没有越界，就更新一下ans
        ans=Math.max(ans,preMax+banks[right].money);
    }
    //接着移动left，直到right-left<d
    while(right<n && left<right && banks[right].location-banks[left].location>=d){
        left++;
        preMax=Math.max(preMax,banks[left].money);
    }
}
return ans;

但是这不是不能AC的根本原因，具体是啥我也不清楚

1024
x