USACO 1.3.2 – Barn Repair

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int main() {
	ofstream fout("barn1.out");
	ifstream fin("barn1.in");
	vector<int> cows, gaps;
	int M, S, C, c, N, stalls = 0;
	fin >> M >> S >> C >> c;
	for (int i = 0; i < C; i++, fin >> c)
		cows.push_back(c);
	sort(cows.begin(), cows.end());
	for (size_t i = 0; i < cows.size() - 1; i++)
		gaps.push_back(cows[i + 1] - cows[i] - 1);
	sort(gaps.begin(), gaps.end(), greater<int> ());
	N = stalls = C;
	while (N > M && N--) {
		stalls += gaps.back();
		gaps.pop_back();
	}
	fout << stalls << endl;
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: