1700回バックアップ:複数タブのスケジュール

9581 ワード
ps cpp greedy テキストリンク

複数のタブの配置


1700回バックアップ:複数タブのスケジュール

アイデア


もし次の電気用品が今多機能ラベルに挿入されていない場合は、挿入された電気用品の中で後で再び現れる電気用品を見つけて、彼女を選ぶことができます.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

int N, K;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> K;
    vector<int> v(K);
    for (int i = 0; i < K; i++) {
        cin >> v[i];
    }

    vector<int> cur;
    auto iter = v.begin();
    // 맨 처음 N개 꽂기
    while (iter != v.end() && cur.size() != N) {
        if (find(cur.begin(), cur.end(), *iter) == cur.end()) {
            cur.push_back(*iter);
        }
        iter++;
    }

    int ans = 0;

    while (iter != v.end()) {
        // 다음 전기용품이 멀티탭에 없으면
        if (find(cur.begin(), cur.end(), *iter) == cur.end()) {
            auto k = iter;
            int target = -1;
            for (int i = 0 ; i < N; i++) {
                // 꽂혀있는 전기용품중 가장 나중에 다시 등장할 전기용품을 찾는다
                auto nk = find(iter, v.end(), cur[i]);
                if (nk > k) {
                    k = nk;
                    target = i;
                }
            }
            // 가장 나중에 등장하는 전기용품 뽑고 다음 전기용품 꽂기
            cur[target] = *iter;
            ans++;
        }
        iter++;
    }

    cout << ans;

    return 0;
}

おしゃべり


難しすぎます...しばらくは高度なアルゴリズムを少し置いて、Greyのような問題を解決しようと努力します.
持続可能なコードの作成
アルゴリズムBasc-2-