链接：https://ac.nowcoder.com/acm/contest/315/D
来源：牛客网
 

题目描述

妞妞参加完Google Girl Hackathon之后,打车回到了牛家庄。

妞妞需要支付给出租车司机车费s元。妞妞身上一共有n个硬币，第i个硬币价值为p[i]元。

妞妞想选择尽量多的硬币，使其总价值足以支付s元车费(即大于等于s)。

 

但是如果从妞妞支付的这些硬币中移除一个或者多个硬币，剩下的硬币总价值还是足以支付车费的话，出租车司机是不会接受的。例如: 妞妞使用价值为2，5，7的硬币去支付s=11的车费,出租车司机是不会接受的，因为价值为2这个硬币是可以移除的。

 

妞妞希望能选取最大数量的硬币，使其总价值足以支付车费并且出租车司机能接受。

妞妞希望你能帮她计算最多可以支付多少个硬币。

输入描述:

输入包括两行, 第一行包括两个正整数n和s(1 <= n <= 10, 1 <= s <= 1000), 表示妞妞的硬币个数和需要支付的车费。
第二行包括n个正整数p[i] (1 <= p[i] <= 100)，表示第i个硬币的价值。
保证妞妞的n个硬币价值总和是大于等于s。

输出描述:

输出一个整数, 表示妞妞最多可以支付的硬币个数。

示例1

输入

5 9
4 1 3 5 4

输出

3

思路：

      先把硬币按照从小到大排序，相加直到相加和大于等于车费，并记录一下这时的下标，然后再从大到小排序，从刚才记录下标开始减少硬币，如果减少其中的硬币还是大于等于车费，就把这个硬币减去，直至结尾。

     这个题的数据量比较小只到10，可以用排序做。

代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
int cmp(int x,int y)
{
	return x > y;
}
int main()
{
	int n,s,i,q,sum,sum1;
	int c[11];
	while(scanf("%d%d",&n,&s)!=EOF)
	{
		sum=sum=0;
		q=0;
		for(i=0;i<n;i++)
			scanf("%d",&c[i]);
		sort(c,c+n);
		for(i=0;i<n;i++)
		{
			sum+=c[i];
			if(sum>=s)
			{
				q=i;
				break;
			}
		}
		sort(c,c+n,cmp);
		for(i=n-q-1;i<n;i++)
		{
			sum1-=c[i];
			if(sum1>=s)
			{
				q--;
				sum-=c[i];
			}
			sum1=sum;
		}
		printf("%d\n",q+1);
	}
	return 0;
}