[BOJ]1461号図書館

名図書館<クリック問題!

𕼧問題の説明

勢俊和の本の位置は0です.本を元の場所に戻すときに、本を元の場所に戻すときに必要な最小ステップ数を計算します.

入力
:本の数N、一度に取れる本の数M(1<=N、M<=50)
:本の位置(0なし、割引が10000以下の整数)

しゅつりょく
:最小ステップ数

条件
:1ステップ=座標1グリッド
本の位置はすべて整数です
本を全部元に戻せば、もう0に戻る必要はありません.一番遠い位置は戻らないでください.

コア原理

Greedy Algorithm 参考資料
:選択した瞬間、目の前に現れる最良の状況だけを追求します.
その瞬间、地域的にはベストだが、最终的な选択にはベストな保障はない!
=>そのため、GRADYアルゴリズムを適用するには、地域性、グローバル性の最適な問題を解決する必要があります!!
:前の選択は後の選択に影響を与えるべきではなく、局所問題に対する最適解は問題全体に対する最適解であるべきである.

原理

:勢俊は本を一度置いて往復する==一番遠いところは往復できない.
:勢俊は一度本を置いて、遠いところを基準に往復します.
==このとき,本の個数はM巻を基準として繰り返される.
==このとき、本の位置が少ないところから往復するのはグリディではありません.
一度本を置いて、一番遠いところから、一人M冊ずつ整理します.

💻コード#コード#

正数部分と負数部分を分けて、節価距離が大きいことから、節価距離を加えることがポイント!

vectorのbegin()、end()はiterator、front()、back()はその要素を返すことを覚えておく~

初めて

include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


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

    int N, M;
    cin >> N >> M;
    vector<int> pos; // 양수 배열
    vector<int> neg; // 음수 배열 
    int sum = 0;

    int temp = 0;
    for (int i = 0; i < N; i++) {
        cin >> temp;
        if (temp > 0) {
            pos.push_back(temp); // 양수 추가
        }
        else {
            neg.push_back(temp); // 음수 추가 
        }
    }

    sort(neg.begin(), neg.end()); // 오름차순 
    sort(pos.begin(), pos.end());   

    int i = 0;
    while (i < neg.size()) {
        sum -= 2*neg[i]; // 절댓값을 더해줘야 하니까
        i += M; // M만큼 증가 
    }

    int j = pos.size()-1; // 인덱스는 i-1번째니까
    while (j > 0) {
        sum += 2*pos[j]; // 더해줌 
        j -= M;
    }

    if (-neg.front() > pos.back()) { 
        cout << sum + neg.front();
    }
    else {
        cout << sum - pos.back();
    }

    return 0;
}

問題の原因
例の1501人をテストしたところ、次のエラーが発生しました.
つまり、空ベクトルのfront()を呼び出しています!

もちろんifとelseを用いて問題を解決することはできるが,判断が不十分であるためコードを変更することにした.

2回目

正負分離をせずに1ベクトル上で計算する

カウントマイナス

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


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

    int N, M;
    cin >> N >> M;
    vector<int> v; // 전체 배열 
    int sum = 0;
    int temp = 0;
    int count = 0;

    for (int i = 0; i < N; i++) {
        cin >> temp; 
        v.push_back(temp); // 양수 추가
        if (temp < 0) {
            count++; // 음수 개수 count 
        }
        
    }
    sort(v.begin(), v.end()); // 내림차순

    for (int i = 0; i < count; i += M) {// M만큼 증가 
        sum -= 2*v[i]; // 절댓값을 더해줘야 하니까
    }

     // 인덱스는 i-1번째니까
    for(int i = v.size()-1; i>= count;i -= M){
        sum += 2 * v[i]; // 더해줌 
    }

    if (abs(v.front()) < abs(v.back())) { //절댓값으로 바로 비교 
        cout << sum - abs(v.back());
    }
    else {
        cout << sum - abs(v.front());
    }

}

逆に時間が短縮され、コードも簡潔になります.