很多题解没有处理只剩一个纪念品的边界情况
查看原帖
很多题解没有处理只剩一个纪念品的边界情况
117972
从蒟蒻到小犇楼主2025/1/5 22:43

题解里排序后双指针的做法的代码

    while(l<=r)//一定要有等号。
    {
        if(a[l]+a[r]<=W)   //一定要有等号。
          l++,r--,ans++;
        else
          r--,ans++;   //贪心过程
    }

应该改成

    while(l<=r)//一定要有等号。
    {
        if(l==r) {
          ans++;
          break;
        }
        if(a[l]+a[r]<=W)   //一定要有等号。
          l++,r--,ans++;
        else
          r--,ans++;   //贪心过程
    }

判断只剩一个纪念品的边界情况,因为一个纪念品不能复制一个装成一组

在这道题里这个代码不判断边界情况其实对结果没有任何影响,都是ans++,算是歪打正着了。不过逻辑不对,换一道题可能就错了

2025/1/5 22:43
加载中...