纪念品分组 题解

类似于双指针的解法，在头尾分别设置l,r。
如果a[l]+a[r]>w的话，说明过大，只能把a[r]单独分为一组，记录次数的sum++；
如果小于等于的话，就l++,r--,sum++;
最后如果l==r的话，就把这一个单独分为一组，sum++；

import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
    public static void main(String args[])throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int w = (int)in.nval;
        in.nextToken();
        int n = (int)in.nval;
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            in.nextToken();
            a[i] = (int)in.nval;
        }
        Arrays.sort(a);
            int l=0,r=n-1,sum=0;
        while(l<r)
        {
            while(a[l]+a[r]>w)
            {
                r--;
                sum++;
            }
            if(a[l]+a[r]<=w)
            {
                l++;r--;
                sum++;
            }
        }
        if(l==r)
            sum++;
        out.println(sum);

        out.flush();
    }
                  }