11399-ACM-Greedyアルゴリズム

5185 ワード
白駿銀器を破壊する テキストリンク

質問する



質問リンク:https://www.acmicpc.net/problem/11399

ポリシー

  • 一人当たりの引き出しに要する時間の最大値
    • を求めます
  • 団の後ろでお金を出している人は、前の人がお金を出すまで待たなければなりません.そのため、最高値を求めるために、お金を引き出すのにかかる時間が少ない人から、順番に取り出すのが最も効率的です.
    • これは引き出し時間の短い人から引き出しを始めるグリディアルゴリズムです.

    コード#コード#

    #include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

int N;
vector<int> p;


int main(){

    // freopen("../input.txt","rt",stdin);
    
    scanf("%d",&N);
    int tmp;
    for(int i=0; i<N; i++){
        scanf("%d",&tmp);
        p.push_back(tmp);
    }

    sort(p.begin(), p.end());
    // 부분합을 만들어 이전 사람들까지 인출할때 걸렸던 모든 시간을 저장한다.
    int pSum = 0;
    int res = 0;

    for(int i=0; i<N; i++){
        pSum += p[i];
        res += pSum;
    }

    printf("%d\n",res);

    return 0;
}

    感想


    実際、グリンディアルゴリズムは目の前の最良の状況だけを追求するアルゴリズムである.まだまだ深くはありませんが、しっかり勉強しなければなりません.
    [アルゴリズム]プログラマー-クレーン型綱引きゲーム/Java
    Java問題1(国別コース)