BAPC 2019 E. Efficient Exchange 思维+ 贪心

Dear 丶 2023-07-18 04:49 7阅读 0赞

题目链接：https://nanti.jisuanke.com/t/44331  
题意：你有无限的1,10,100……金钱，现在你要花费n元，你的代价是花费的金币数和找零的金币数之和，求最小代价  
思路：对于小于5的位肯定是直接付比较优，大于5的话肯定是付10这种更优，等于5的时候需要特判一下如果  
进位对前面的位是否更优，更优的话(a\[i - 1\] >= 5) 就进位就行了

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define fi first
    #define se second
    #define ls rt << 1
    #define rs rt << 1|1
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    #define pll pair<ll, ll>
    #define pii pair<int, int>
    #define ull unsigned long long
    #define pdd pair<double, double>
    const int mod = 998244353;
    const int maxn = 3e4 + 10;
    const int inf = 0x3f3f3f3f;
    char s[maxn];
    int a[maxn];
    
    int main()
    {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        for(int i = 1; i <= n; ++i) a[i] = s[i] - '0';
        int pre = 0, sum = 0;
        for(int i = n; i >= 1; --i)
        {
            a[i] += pre;
            pre = 0;
            if(a[i] > 5)
            {
                pre = 1;
                sum += 10 - a[i];
            }
            else if(a[i] == 5)
            {
                if(a[i - 1] >= 5)
                    pre = 1;
                sum += 5;
            }
            else sum += a[i];
        }
        sum += a[0] + pre;
        printf("%d\n", sum);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，7人围观）

还没有评论，来说两句吧...

相关阅读

相关【贪心】CF1822 E

[Problem - 1822E - Codeforces][] 题意： ![2e9c008736434bd3aade35f13ba3671b.png][] ![e793

女爷i/ 2024年03月23日 23:48/ 0 赞/ 100 阅读

相关思维+贪心——cf1042D

/ 首先考虑从后往前计算lis，显然0的在很多情况下的贡献要大于1 如果遇上0，那么lis++，如果遇上1，那么cnt1++，并且用cnt1更新lis

一时失言乱红尘/ 2023年10月11日 09:09/ 0 赞/ 47 阅读

相关 BAPC 2019 F. Find my Family set + 二分

题目链接：https://nanti.jisuanke.com/t/44322 题意：给你n个数的序列，问你是否存在ai > aj, aj < ak, ai < ak, i

一时失言乱红尘/ 2023年07月18日 04:50/ 0 赞/ 7 阅读

相关 BAPC 2019 E. Efficient Exchange 思维+ 贪心

题目链接：https://nanti.jisuanke.com/t/44331 题意：你有无限的1,10,100……金钱，现在你要花费n元，你的代价是花费的金币数和找零的金

Dear 丶/ 2023年07月18日 04:49/ 0 赞/ 8 阅读

相关 BAPC 2019 A. Appeal to the Audience 贪心 + DFS

题目链接：https://nanti.jisuanke.com/t/44317 题意：给你一棵树和k个值，要把这k个值放在k个叶子结点上，而对每个非叶子结点来说它的值

╰半夏微凉°/ 2023年07月18日 04:48/ 0 赞/ 5 阅读

相关 codeforces 1058E (思维)

[传送][Link 1] 题意：给n个数，每个数的二进制1都可以随意的换位置，问区间异或为0的有多少个思路：该问题可以转化为他的充要条件： 1.区间1的个数为偶数 2

迈不过友情╰/ 2022年05月10日 12:56/ 0 赞/ 216 阅读

相关 Codeforces 353E 贪心

题意：给你一张有向图，第i条边连接i号点和(i + 1) % n号点，问最多可以选择多少个点，使得这些点互相不可达。思路：容易发现，如果某个边的集合点的数目大于等于2，那么

妖狐艹你老母/ 2021年12月12日 02:04/ 0 赞/ 257 阅读

相关 C. Canine poetry (贪心、思维)

[题目][Link 1] 思路：首先可以知道如果我们要消灭长度>=4的回文串，那么这个大的回文串必然包含小的回文串。所以我们其实只要消灭小的回文串就可以了。其实就

谁借莪１个温暖的怀抱￠/ 2021年07月17日 01:19/ 0 赞/ 404 阅读

相关 C. Basic Diplomacy （思维、贪心）

[题目][Link 1] 思路：首先为NO的情况只有，某一天只可以选一个人且某人在只可以选他的情况下被选了>⌈m2⌉次。除了这种情况，其它情况不可能为NO，看一个极端的例

谁践踏了优雅/ 2021年07月16日 23:17/ 0 赞/ 421 阅读

相关 C. Maximum width (贪心、思维)

[题目][Link 1] 思路：对于答案我们只需求取每相邻的两个元素的最大相差再从所有的最大相差取最大的即可，那么贪心一下假如要求取的是第一个和第二个元素的最大相差，那么

朴灿烈づ我的快乐病毒、/ 2021年07月16日 23:12/ 0 赞/ 409 阅读