平等交易

问题描述

你有 nn 件道具可以买，其中第 ii 件的价格为 a_ia i 。

你有 ww 元钱。你仅能用钱购买其中的一件商道具。当然，你可以拿你手中的道具换取其他的道具，只是这些商道具的价值之和，不能超过你打算交换出去的道具。你可以交换无数多次道具。道具的价值可能是 00，但是你不能使用空集换取价值为 0 的商品。

请问，在这个条件下，最多可以换取多少件道具？ 输入格式 第一行一个正整数 nn，表示道具个数。

接下来一行 nn 个正整数，表示 {a_n}{a n}。

接下来一行 11 个正整数，表示 ww。

输出格式 一个正整数，表示答案。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+10;
int a[N];
int main ()
{
	int n;cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    ll w;cin>>w;
    sort(a,a+n);
    int k=0;
    for(int i=n-1;i>=0;i--) 
    {
    	if(a[i]<w)
        {
        	k=a[i];
            break;
        }
     }
     int ans=0;
     for(int i=0;i<n;i++)
     {
     	if(a[i]<=k)
        {
        	ans++;
            k-=a[i];
        }
      }
      cout<<ans<<endl;
      return 0;
}