[Luogu P1658] 购物

这道题的主要思想是贪心。

题目的要求用几个硬币将1~x的数都能够凑出的最少硬币个数。这里注意一下是都凑出而不是同时凑出。

先讨论什么时候无解。所有的自然数都可以用1堆砌而成。换而言之只要有1这个流氓在就可以凑齐。没有1就凑不出来1。

我们用一个数num表示我们目前凑完了sum这个数，准备凑下一个，要开始拿钱了，并且对于所有p（p<=sum）都能刚好凑出，又对于所有g（g>sum）凑不出。

那么我们这个时候要怎么拿钱呢。运用贪心思想，尽可能拿大的。那么什么时候是不可能的呢？即这个硬币q>sum+1时。因为这样就没有方法能够通过这个硬币与之前的凑出sum+1.

所以我们只需要选择q<=sum+1的同时q尽量大的硬币，这样子保证了q~sum+q都能被凑出。此时sum=sum+q

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int read(){

    int res=,f=;

    char ch=getchar();

    while(ch<''||ch>''){

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<=''){

        res=res*+(ch-'');

        ch=getchar();

    }

    return res*f;

}

int x,n,a[],sum,ans;

int main(){

    x=read();n=read();

    for(int i=;i<=n;++i){

        a[i]=read();

    }

    sort(a+,a+n+);

    if(a[]!=){

        cout<<"-1";

        return ;

    }

    while(sum<x){

        int i;

        for(i=n;i>=;i--)

            if(a[i]<=sum+)break;

        ans++;

        sum+=a[i];

    }

    cout<<ans;

}

巴特西

[Luogu P1658] 购物

最新文章

热门文章