解题思路:
双指针,通过两个变量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 人评分
【绝对值排序】 (C语言代码)浏览:780 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:550 |
【计算两点间的距离】 (C语言代码)浏览:905 |
十->二进制转换 (C语言代码)浏览:1319 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:663 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:774 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:397 |
三角形 (C++代码)递推浏览:791 |
C语言考试练习题_保留字母 (C语言代码)浏览:725 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:343 |