| by XianKa | No comments

【19HDU多校】Rikka with Coin,贪心

传送门

题意是说有面值10 20 50 100的钱,有n个价格给定的菜,要求用最少的硬币数量,使得所有n个菜品的价格都能被凑出来。

贪心:直观想法是先用大的面值,依次用小的面值。

这样的话可以发现10, 20, 20, 50四个面值能凑出所有100以内的价格。

但是有个例外:90 110 这样的数据,如果按照上面的贪法是100 50 20 20 10五个硬币,实际上只需要50 20 20 20四个硬币就可以拼出来。

所以进一步发现用10 20 20 20 50五个硬币可以包含所有最优方案。两个10肯定能用一个20代替,四个20肯定能用一个50 20 10代替。

所以做一个10 20 20 20 50的子集生成。然后暴力判断dish[i] % 100 + 100dish[i] % 100在某个组合的子集生成里有没有。(有先后顺序,第一个如果有了第二个就不用判断。因为既然零钱数量是固定的,那么100圆的越少约好)如果有,100圆的数量就分别是(dish[i] - (dish[i] % 100 + 100)/ 100) ,和dish[i] / 100

对于100圆判断是个重要细节。
比如1000 90 110这样的数据,1000其中的100圆可以用零钱拼出来,所以100圆个数只有9个。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5] = {10, 20, 20, 20, 50};
int b[10], n;
ll d[210];
set<int> st[1 << 6];
void dfs(set<int> &t, int now, int sum)
{
    t.insert(sum);
    //if(now > n) return;
    while(now < n)
    {
        ++now;
        dfs(t, now, sum + b[now]);
    }
}
int main()
{
    freopen("02.in", "r", stdin);
    for(int i = 1; i < 1 << 5; i++)
    {
        n = 0;
        for(int j = 0; j < 5; j++)
        {
            if(1 & (i >> j)) b[n++] = a[j];
        }
        n--;
        for(int j = 0; j <= n; j++) dfs(st[i], j, b[j]);
    }

    // for(int i = 1; i < 1 << 5; i++)
    // {
    //     cout << i << ':';
    //     for(auto it = st[i].begin(); it != st[i].end(); it++) cout << *it << ' ';
    //     cout << endl;
    // }
    int T; cin >> T;
    while(T--)
    {
        int num; scanf("%d", &num);
        int flag = 0;
        for(int i = 1; i <= num; i++) 
        {
            scanf("%lld", &d[i]);
            if(d[i] % 10) flag = 1;
        }
        //sort(d + 1, d + 1 + num);
        if(flag)
        {
            printf("-1\n");
            continue;
        }
        ll ans = 1e12;
        for(int i = 0; i < 1 << 5; i++)
        {
            if(i == 23)
            {
                int debug = 1;
            }
            int cz = __builtin_popcount(i);
            ll dol = 0;
            int can = 1;
            for(int j = 1; j <= num; j++)
            {
                if(d[j] >= 100)
                {
                    int tmp = d[j] % 100;
                    tmp += 100;
                    if(st[i].find(tmp) != st[i].end()) 
                    {
                        dol = max((d[j] - tmp) / 100, dol);
                        continue;
                    }
                }
                if(st[i].find(d[j] % 100) != st[i].end()) dol = max(d[j] / 100, dol);
                else if(d[j] % 100 == 0) dol = max(d[j] / 100, dol);
                else can = 0;  
            }
            if(can == 0) continue;
            //ans = min(ans, dol + cz);
            if(ans > dol + cz) ans = dol + cz;
        }
        cout << ans << endl;
    }
}
//23:10 20 30 40 50 60 70 80 90 100

// 110 70 190
// 1010 90 110

发表评论