洛谷P1094 纪念品分组（Java）

题目

注：90分，超时错误一个，请大佬指教。

输入输出样例
输入：

100 
9 
90 
20 
20 
30 
50 
60 
70 
80 
90

输出

6

思路：

1，从大到小排序
2，两个标记i,j分别从数组往后和往前，如果v[i]+v[j]比给定的值要小，这两个就算一个，结果加一；如果v[i]+v[j]比给定的值要大，就只要大的那个，让它单独一组，小的继续往后找。

代码

package 贪心;

import java.util.Arrays;
import java.util.Scanner;

public class P1094纪念品分组 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int w=sc.nextInt();
        int n=sc.nextInt();
        int[] v=new int[n];
        for (int i = 0; i < n; i++) {
            v[i]=sc.nextInt();
        }
        Arrays.sort(v);
        int cnt=0;
        //思路对了，但是实现方法不对，别用双重for循环，用两个变量标记
        int i=0,j=n-1;
        while (i<=j){
            if (v[i]+v[j]<=w){
                cnt++;
                i++;
                j--;
                continue;
            }else{
                cnt++;
                j--;
                continue;
            }
        }
        System.out.println(cnt);
    }
}