Yukicoder083 最大マッチング

問題概要

あなたは「最大マッチング問題」という有名問題に取り組んでいる。
これは、何本かのマッチ棒が与えられたとき、それらを並べて表記できる最大の数を求める問題である。
数の表記は、0 から 9 までの数字を横に並べることによって行う。
マッチ棒は折ってはいけないが、すべて使い切る必要はない。
さて、$N$本のマッチ棒が与えられたとき、それらを並べて表記できる最大の数を求めよ。

$2\leqq N\leqq10^5$

yukicoder083

解法

1をたくさんつくって奇数本余ったら7に書き換えると長い文字列を作ることができる。
エド・はるみさんを思いだした…

計算量:$O(1)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        int N; cin >> N;
        if (N % 2 == 0) {
            cout << string(N / 2, '1') << endl;
        }
        else {
            cout << "7" << string((N - 3) / 2, '1') << endl;
        }
    
        return 0;
    }