[BOJ/C+]20921号の関係

8756 ワード
boj greedy cpp テキストリンク
今回の問題はGreedyアルゴリズムを用いて解決した.まず、ルールを見つけることが大切です.
  • viが持つことができる関係はn-i個である.
  • は0からn−1まで繰り返し加算してkを生じる問題である.
  • kの範囲が0以上、n−1以下の場合、k+1の値を1つ前に入力するだけで解決できる.
  • kがnと2 n−1の間にある場合、n−1と残りの数の一方の位置を前方に移動させることができる.
  • kが2 n−2と3 n−6の間にある場合、n−1、n−2と残りの数のうちの1つの位置を移動するだけでよい.
  • kの範囲によれば、選択の数を増やし続けると、すべてのkのn(n−1)/2を作成することができる.
  • 、kをn−1から比較し、kがこの数より大きい場合、kからこの数を減算することを繰り返す.
  • n-iが必要な場合は、n-i+1を順番に列の最初の左側から充填し、この操作が完了したら、残りの数を昇順に空白に配置します.
  • アクセスの配列チェックは数字を使用します.

    • Code

    #include <iostream>
#include <cstring>
#define MAX 4243
using namespace std;

int n, k;
int v[MAX];
bool visited[MAX];

void Input(){
    cin>>n>>k;
    memset(v, 0, sizeof(v));
    memset(visited, false, sizeof(visited));
}

void Solution(){
    int end=n;
    int idx=1;
    while(k){
        if(k>=end-1){
            k-=(end-1);
            v[idx]=end;
            idx++;
            visited[end]=true;
        }
        end--;
    }
    int num=1;
    for(int i=1; i<=n; i++){
        if(v[i]!=0) continue;
        while(visited[num])
            num++;
        v[i]=num++;
    }
}

void Solve(){
    for(int i=1; i<=n; i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    Solve();
    return 0;
}
    CodeKata 17
    Linux 3日目03