P8444 题解

_Give_up_ · 2022-07-25 19:22:57 · 题解

题目传送门

题目思路

此题就是一道简单的贪心，先从小到大排序（也可以从大到小），取能买的起的最贵的物品。

找到后从小到大遍历，求能买的起的价值最高的的物品最多能换到多少其他的物品，用一个计数器计数，最后输出这个计数器的值就行了。

代码

#include<bits/stdc++.h>
#define int long long //a[i]的范围很大，要开long long
#define N 1000010

using namespace std;

typedef long long ll;

int read()
{
    int x = 0,f = 1;
    char c = getchar();
    while(c<'0' || c>'9')
    {
        if(c=='-') f = -1;
        c = getchar();
    }
    while(c>='0' && c<='9')
    {
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
    return x*f;
}//快读

int a[N];

signed main()
{
    int n=read();
    for (int i=1;i<=n;i++)
        a[i] = read();
    int w=read(),k=0;
    sort(a+1,a+n+1); //从小到大排序
    for (int i=n;i>=1;i--)
    {
        if (w>=a[i])
        {
            k = a[i];
            break;
        }
    }//求能买的起的最贵的物品
    int ans = 0;//定义一个计数器，初始值为0
    for (int i=1;i<=n;i++)
    {
        if (k>=a[i])
        {
            ans++;//计数器+1
            k -= a[i];
        }
    }//求能买的起的价值最高的的物品最多能换到多少其他的物品
    cout << ans << endl;//输出计数器的值
    return 0; 
}