[USACO] 1.3 Barn Repair(Greedy Algorithm)

목재개수 m이 충분할 경우를 고려하지 않아서 한번 틀렸다.
Greedy 알고리즘을 적용하여, 가장 간격이 큰 것부터 나눠나가면 된다.

int main() {

    ofstream fout ("barn1.out");
    ifstream fin ("barn1.in");

    int m, s, c;
    fin >> m >> s >> c;

    vector<int> cow;
    REP(i, c)
    {
        int a;
        fin >> a;
        cow.pb(a);
    }
    sort(ALL(cow));

    vector< pair<int, int> > d;
    d.pb( make_pair(0, cow[0]) );

    for(int i=1; i< cow.size(); i++) d.pb( make_pair(cow[i]-cow[i-1], cow[i]) );
    sort(d.rbegin(), d.rend());

    vector<int> f;
    REP(i, m-1)    f.pb(d[i].second);
    sort(ALL(f));

    int ret = 0, start = 0;
    REP(i, f.size())
    {   
        for(int j=start; j < cow.size(); j++)
        {
            if( cow[j] == f[i] )
            {
                ret += cow[j-1] - cow[start] + 1;
                start = j;
                break;
            }
        }
    }
    ret += cow[cow.size()-1] - cow[start] +1 ;

    if( m >= c ) fout << c << endl;
    else fout << ret << endl;
   
    return 0;
}