Gym 10102B 贪心

原题连接:http://codeforces.com/gym/101102/problem/B

题意:用火柴棍摆数字,保证位数不变的情况下,相同数量的火柴棍,使数值尽量大。

思路:先建立一个数组,对应每一个数字需要的火柴棍数量。外层循环枚举每一位,内层循环选数字。每一位数字最少用2根火柴棍,最多用7根,所以剩下几位,就用位数乘以2作为下限,乘以7作为上限,只需判定选用本次数值后剩下的火柴棍是否再上下限范围内,即可完成判定。

完整代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100005

char s[N];
int d[10]={6,2,5,5,4,5,6,3,7,6};
int main(){
    int t,n;
    scanf("%d",&t);
    while(t--){
        int sum=0;
        scanf("%d%s",&n,s);
        for(int i=0;i<n;i++){
            sum+=d[s[i]-'0'];
        }
        for(int i=1;i<=n;i++){
            int l=(n-i)*2,r=(n-i)*7;
            for(int j=9;j>=0;j--){
                int a=sum-d[j];
                if(a>=l&&a<=r){
                    sum-=d[j];
                    printf("%d",j);
                    break;
                }
            }
        }
        printf("\n");
    }
    return 0;
}

 

上一篇:codeforces gym #101161F-Dictionary Game(字典树+树上删边游戏)


下一篇:MSF——信息收集(四)