poj2487

package easy;


import java.io.BufferedInputStream;
import java.util.Scanner;

/**
 *
 *poj2487
 * @author NC
 */
public class Poj2487 {

    private static int partition(int[] array, int low, int high) {
        int key = array[low]; //用子表的第一个记录作为枢轴记录
        while (low < high) {//从表的两端交替地向中间扫描
            while (low < high && array[high] >= key) {//比枢轴记录大的话，位置正确，移动下标
                high--; //下标从高端向中间扫描
            }
            array[low] = array[high]; //把比枢轴记录小的记录交换到低端,（这里先从直接赋值，和下面的一起才算交换）
            while (low < high && array[low] <= key) {//比枢轴记录小的话，位置正确，移动下标
                low++; //下标从低端向中间扫描
            }
            array[high] = array[low]; //把比枢轴记录大的记录交换到高端，（这里赋值回去，和上面的一起才算交换）
        }
        array[low] = key; //枢轴记录到位
        return low;
    }

    private static void qSort(int[] array, int low, int high) {
        int pivotloc;
        if (low < high) {//保证长度大于1，递归的出口
            pivotloc = partition(array, low, high); //将表low-high一分为2，用枢轴位置来分
            qSort(array, low, pivotloc - 1); //对低子表递归排序
            qSort(array, pivotloc + 1, high); //对高子表递归排序
        }
    }

    private static void quickSort(int[] array) {
        int n = array.length - 1;//注意这里
        qSort(array, 1, n);
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedInputStream(System.in));
        if (scan.hasNext()) {
            int n = scan.nextInt();
            for (int i = 1; i <= n; i++) {
                int stamps = scan.nextInt();
                int friends = scan.nextInt();
                int[] fs = new int[friends + 1];
                for (int j = 1; j <= friends; j++) {
                    fs[j] = scan.nextInt();
                }
                quickSort(fs);
                int count = 0;
                int sum = 0;
                for (int k = friends; k >= 1; k--) {
                    if (sum < stamps) {
                        sum = sum + fs[k];
                        count++;
                    } else {
                        break;
                    }
                }
                if (sum < stamps) {
                    System.out.println("Scenario #" + i + ":");
                    System.out.println("impossible");
                    System.out.println();
                } else {
                    System.out.println("Scenario #" + i + ":");
                    System.out.println(count);
                    System.out.println();
                }

            }
        }
    }
}