题解 | #[NOIP2007]纪念品分组#

阅读完此题，你会发现，解决此题的关键是如何让两个数“尽可能”相加成一个值，这个值要小于等于w(w为每组纪念品价格之和的上限)，所以，我们要做的是便是如何“凑出”这个数，我们可以先把这些数放入一个数组中，然后通过数组中的sort()方法对数组进行排序，使其从小到大的排列，接下来我们要做的是“凑数”，我们可以利用两个for循环，i的那一层循环控制数组头指针，j的那一层循环控制数组尾指针，使得s[i]+s[j]<=w;满足的我们便用计数器进行计数，并且s[i]、[j]重新赋值0，代表已经组队，对不满足s[i]+s[j]<=w的我们先进行“预留”，后期再用for循环进行遍历，这些“预留的数”都是为单个数(无法组队)，所以我们再用计数器自加一即可完成此题

import java.util.*; public class Main {

public static void main(String[] args) {
	// TODO Auto-generated method stub
	Scanner sc=new Scanner(System.in);
	int w=sc.nextInt();
	int n=sc.nextInt();
	int[] s=new int[n];
	int count=0;
	for(int i=0;i<n;i++) {
		s[i]=sc.nextInt();
	}

	Arrays.sort(s);

	for(int i=0;i<n-1;i++) {
		for(int j=n-1;j>i;j--) {
			if(s[i]+s[j]<=w && s[i]>=5 && s[j]>=5) {
				s[i]=0;
				s[j]=0;
				count++;
				j=i;
			}
		}
	}
	
	for(int i=0;i<n;i++) {
		if(s[i]>=5) {
			count++;
		}
		
	}
	System.out.print(count+" ");
}

}