首页 » 未分类 » 正文

NKOJ 3847 (贪心)

文章使用了传送门,侵权可联系删除。

P3847

问题描述

Mr_he 因讨厌XXX而彻底放弃网购,他的日常用品都要到商场去购买,而且必须付现金。但是现 金购买,经常会遇到找零的问题,那么现在请你帮助他解决这样一个问题: 现在 Mr_he 手上有 n 种不同面值的硬币,每种硬币有无限多个。为了方便购物,他希望带尽量 少的硬币,但是要能组合出 1 到 m 之间的任意值。

输入格式

第一行为两个整数:m 和 n,他们的意义如题目描述。
接下来的 n 行,每行一个整数,第 i+1 行的整数表示第 i 种硬币的面值

输出格式

最少需要携带的硬币数量,如果无解则输出-1。

样例输入

20 4
1
2
5
10

样例输出

5

数据范围

50%的数据:1<=n<=10, 1<=m<=10^3;
100%的数据:1<=n<=100,1<=m<=10^9;

解法

此题看上去像背包,然而范围太大,没有什么好方法可以处理。

没什么好方法的时候就应该考虑贪心。

考虑1−i已经构出,那么再加一枚什么面值的硬币最优,显然选一枚<=sum+1且面值最大的即可。面值最大保证了硬币数最小。sum表示硬币面值和。

事实上,这个贪心可以从F[i]=F[i−A[k]]+1看出。F[i]必然是单调增的,因此贪心即可。F[i]表示处理完1−i的最少硬币数

这个算法有问题:在m=1e9、n=1且硬币值为1的时候会超时。
错误代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,A[105],sum,cnt;
int main()
{
    int i,j,k;
    scanf("%d%d",&m,&n);
    for(i=1;i<=n;i++)scanf("%d",&A[i]);
    sort(A+1,A+n+1);
    if(A[1]!=1){printf("-1");return 0;}
    sum=1;
    while(sum<m)
    {
        for(i=1;i<=n;i++)if(A[i]>sum+1)break;
        sum+=A[i-1];cnt++;
    }
    printf("%d",cnt+1);
}

尽量用已经选的硬币凑成大面值硬币的面值-1,如果不能恰好凑成就多用一个。时间复杂度降到了O(n)。参考传送门
正确代码

#include<bits/stdc++.h>

using namespace std;  

const int maxn = 1111;  
int arr[maxn];  
int main(){
    int m, n;  
    scanf("%d%d", &m, &n);  
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);  
    }
    arr[n+1]=m+1;  
    sort(arr+1, arr+n+2);  
    if(arr[1] != 1) {
        printf("-1\n");  
        return 0;  
    }
    int tot=0;  //前0个可以 
    int ans =0;  //0个硬币 
    for(int i=2; i<=n+1 && arr[i] <= m+1; i++){  //i时算i-1要多少个,算到arr[i]-1要多少个 
        if(arr[i] <= tot+1) continue;  //tot+1也不要,在这里没用,下面的t会是0 
        int t= ceil((arr[i]-1.0-tot)/arr[i-1]);  
        ans += t;  //t个arr[i-1]
        tot += t*arr[i-1];   
    }
    printf("%d\n", ans);  
} 

发表评论