坚果吞噬者


私信TA

用户名:245336699

访问量:2460

签 名:

等  级
排  名 725
经  验 3785
参赛次数 0
文章发表 10
年  龄 0
在职情况 学生
学  校 邢台学院
专  业 计科

  自我简介:

解题思路:
双指针,通过两个变量i,j分别从左和从右遍历整个数组(需先排序)

当gifts[i] + gifts[j] >w时,说明没有任何一个物品可以和gifts[j]一组还能保证小于限定值w(因为gifts[i]是当前未分配最小的物品了),所以我们让当前最大的物品自己一组,并将j--,更新当前最大物品下标,同时cnt++

当gifts[i] + gifts[j] <=w时,道理同上,只不过这两个可以一组,更新i,j和cnt

注意事项:
当进行判断gifts[i] + gifts[j] 与 w的大小时,需要保证i <= j的先决条件,防止数组越界
参考代码:

import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        int w,n;//w表示最大价值,n表示物品
        int i,cnt=0;
        w = sc.nextInt();
        n = sc.nextInt();
        int[] gifts = new int[n];
        
        for(i = 0;i < n;i++)
            gifts[i] = sc.nextInt();

        Arrays.sort(gifts);//先排序,确定数组有序
        cnt = guo(gifts,w,n);
        System.out.println(cnt);
        

    }

    public static int guo(int[] gifts,int w,int n)
    {
        int i,j;
        int cnt=0;
        i = 0;//左指针
        j = n-1;//右指针  

        while(i <= j)//当左指针小于等于右指针时,说明物品还没分完,循环继续
        {
            while(gifts[i] + gifts[j] > w &&i <= j)//当当前最小和最大的物品加起来大于限定值时,说明最大的只能自己一组了
            {
                j--;
                cnt++;
            }
            while(gifts[i] + gifts[j] <= w && i <= j)//当当前最小和最大的物品加起来小于等于限定值时,更新最大最小值
            {
                i++;
                j--;
                cnt++;
            }
        }
        
        return cnt;//返回组数
    }
}


 

0.0分

1 人评分

  评论区