Gym – 101102B B. The Little Match Girl 贪心、数论、分步

Source

2016 ACM Amman Collegiate Programming Contest

UESTC 2017 Winter Training #1

Gym - 101102B

My Solution

题意：给一串由火柴构成的数字，可以移动火柴改变数字，使得整个数尽可能大，但不能增加或减少数位。

贪心、数论、分步

每个数字的火柴数分别是a[0] = 6, a[1] = 2, a[2] = 5, a[3] = 5, a[4] = 4, a[5] = 5, a[6] = 6, a[7] = 3, a[8] = 7, a[9] = 6;

统计出总火柴数，

优先构造出6，此时要判断if(cnt - 6 * i >= (c - i) * 2 && cnt - 6 * i <= (c - i) * 7 && c)即剩余的火柴必须可以构造至少c-i个1(2)，最多构造c-i个8(7)，

然后构造8(7),if(cnt - 7 * i >= (c - i) * 2 && c)

再构造7(3)，此时要判断if(cnt - 3 * i >= (c - i) * 2 && cnt - 3 * i <= (c - i) * 5 && c) 即剩余的火柴必须最多可以构造c-i个5(5),

然后构造5(5)，4(4)，1(2)。

复杂度 O(n)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;

string s;
int a[10], cnt, ans[10];

int main()
{
    #ifdef LOCAL
    freopen("b.txt", "r", stdin);
    //freopen("b.out", "w", stdout);

    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);
    a[0] = 6, a[1] = 2, a[2] = 5, a[3] = 5, a[4] = 4, a[5] = 5, a[6] = 6, a[7] = 3, a[8] = 7, a[9] = 6;
    int T, n, cnt, c, i, k;
    cin >> T;
    while(T--){
        memset(ans, 0, sizeof ans);
        cnt = c = 0;
        cin >> n >> s;
        for(i = 0; i < n; i++){
            if(a[s[i] - '0'] == 6){
                ans[9]++;
            }
            else{
                cnt += a[s[i] - '0'];
                c++;
            }
        }
        k = cnt / 6;
        //cout << cnt << endl; for(i = min(c, k); i >= 0; i--){
            if(cnt - 6 * i >= (c - i) * 2 && cnt - 6 * i <= (c - i) * 7 && c){ if(i == c){ if(cnt - 6 * i == 0){ ans[9] += i; cnt -= 6 * i; c -= i; break; } } else{ ans[9] += i; cnt -= 6 * i; c -= i; break; } } } k = cnt / 7; for(i = min(k, c); i >= 0; i--){
            if(cnt - 7 * i >= (c - i) * 2 && c){
                if(i == c){
                    if(cnt - 7 * i == 0){
                        ans[8] += i;
                        cnt -= 7 * i;
                        c -= i;
                        break;
                    }
                }
                else{
                    ans[8] += i;
                    cnt -= 7 * i;
                    c -= i;
                    break;
                }
            }
        }

        k = cnt / 3;
        for(i = min(k, c); i >= 0; i--){
            if(cnt - 3 * i >= (c - i) * 2 && cnt - 3 * i <= (c - i) * 5 && c){ if(i == c){ if(cnt - 3 * i == 0){ ans[7] += i; cnt -= 3 * i; c -= i; break; } } else{ ans[7] += i; cnt -= 3 * i; c -= i; break; } } } k = cnt / 5; for(i = min(k, c); i >= 0; i--){
            if(cnt - 5 * i >= (c  - i) * 2 && c){
                if(i == c){
                    if(cnt - 5 * i == 0){
                        ans[5] += i;
                        cnt -= 5 * i;
                        c -= i;
                        break;
                    }
                }
                else{
                    ans[5] += i;
                    cnt -= 5 * i;
                    c -= i;
                    break;
                }
            }
        }

        k = cnt / 4;
        for(i = min(k, c); i >= 0; i--){
            if(cnt - 4 * i >= (c  - i) * 2 && c){
                if(i == c){
                    if(cnt - 4 * i == 0){
                        ans[4] += i;
                        cnt -= 4 * i;
                        c -= i;
                        break;
                    }
                }
                else{
                    ans[4] += i;
                    cnt -= 4 * i;
                    c -= i;
                    break;
                }
            }
        }

        ans[1] = max(0, c);

        for(int i = 9; i >= 0; i--){
            while(ans[i] > 0){
                cout << i;
                ans[i]--;
            }
        }
        cout << endl;



    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx