首页 > 代码库 > Gym 101102B The Little Match Girl(贪心+规律)
Gym 101102B The Little Match Girl(贪心+规律)
这个题目的做法不止一种,solve1:每个数字使用的火柴棒都在2~7之间,而且是连续的,就是2-7之前没有空着的数。这样就有一个结论,在下界为l,上界为r的情况下,假设有n个数,那么火柴棒总数一定在n*l 与n*r之间,首先容易想到这个问题肯定是只关心火柴棒的总数,然后就是一个重新组合的问题,假设第一个重组后的数消耗了x个火柴棒,那么剩下的sum-x如果在(n-1)*l 与 (n-1)*r之间,那么一定可以组合成n-1个数,且最后正好用光,条件是数字必须连续,为什么读者可以自己举样例。 这样从9到1枚举即可了。
solve2:观察这里的数,发现1是一个非常好的数,他是最小的数,并且消耗火柴棒最少,等等……0呢? 0直接无视掉变成9啊……最后的时候其实只会有1,9,7,4,8这几个数,我们可以让他们都变成1,然后把剩下的火柴棒加上去即可,肯定是加4根变成9最好,可以除以4看一下能出多少9,放不满余数只能是0,1,2,3讨论一下即可,放满了说明只能放8,每次加一个,从低位向高位加即可。
总之,第一个算是上下界的结论,第二个是贪心,也是我自己的做法,第二个稍微快一点~
代码如下:
#include<bits/stdc++.h>using namespace std;const int MAXN = 1e5+5;char a[MAXN];int w[10] = {6,2,5,5,4,5,6,3,7,6};int fan[8] = {0,0,1,7,4,5,9,8};void solve1(int n) { int sum = 0,tmp; for(int i = 0; i < n; i++) { sum += w[a[i]-‘0‘]; } for(int i = 1; i <= n; i++) { for(int j = 9; j >= 0; j--) { tmp = sum-w[j]; if(tmp>=2*(n-i) && tmp<=7*(n-i)) { printf("%d",j); sum = tmp; break; } } } printf("\n");}void solve2(int n) { int sum = 0,tmp; for(int i = 0; i < n; i++) { sum += w[a[i]-‘0‘]; a[i] = ‘1‘; } tmp = sum-2*n; int k = tmp/4; int yu = tmp%4; for(int i = 0; i<n&&i<k; i++) { a[i] = ‘9‘; } if(k < n) { if(k == n-1) { a[k] = fan[2+yu]+‘0‘; } else if(k == n-2) { if(yu == 1) a[k] = ‘7‘; if(yu == 2) a[k] = a[k+1] = ‘7‘; if(yu == 3) a[k]=‘7‘,a[k+1] = ‘4‘; } else if(k == n-3) { if(yu == 1) a[k] = ‘7‘; if(yu == 2) a[k] = a[k+1] = ‘7‘; if(yu == 3) a[k] = a[k+1] = a[k+2] = ‘7‘; } else { for(int i = 0; i < yu; i++) { a[k+i] = ‘7‘; } } } else { tmp -= 4*n; int ip = n-1; while(tmp--) { a[ip--] = ‘8‘; } } printf("%s\n",a);}int main() {// freopen("B.in.cpp","r",stdin); int T,n; scanf("%d",&T); while(T--) { scanf("%d%s",&n,a);// solve1(n); solve2(n); } return 0;}
Gym 101102B The Little Match Girl(贪心+规律)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。