neoevoke » [usaco] 1.2 Milking Cows

[usaco] 1.2 Milking Cows - usaco

2009.08.08 19:35 neoevoke Edit

농부가 n명 있는데 각각 일을 시작하는 시간과 끝내는 시간이 다른데 연속으로 일하는 가장 긴 시간과 아무도 일하지 않는 가장 긴 시간을 구하는 문제이다.

시간 interval들을 merge하는 방식으로 해결했다.

/*
ID: neoevok1
PROG: milk2
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    ofstream fout ("milk2.out");
    ifstream fin ("milk2.in");

int n;

fin >> n;

vector<pair<int, int> > v(n);
   	vector<pair<int,int> > times;

for(int i=0;i<n;i++)
	{
		fin >> v[i].first >> v[i].second;
		bool found=false;
		times.push_back(v[i]);

}
	sort(times.begin(), times.end());

for(int i=0;i<times.size();i++)
			for(int j=0;j<times.size();j++)
			{
				if(i==j) continue;
				
				if(times[i].second >= times[j].first && times[j].second>=times[i].first)
				{
					times[i].second = max(times[i].second, times[j].second);
					times[i].first = min(times[i].first, times[j].first);
					times.erase(times.begin()+j);
					i=0;j=0;
				}
			}

int m1=0, m2=0;

for(int i=0;i<times.size();i++)
	{
		m1=max(m1,times[i].second-times[i].first);
		if(i>0)
		{
			m2=max(m2,times[i].first-times[i-1].second);
		}
	}
	fout << m1 << " " << m2 << endl;
	
	return 0;
}

[usaco] 1.2 Transformations [usaco] 1.1 Broken Necklace

Trackbacks 0

엮인글 주소: http://dw.yutar.net/329383/5bb/trackback

Comments 0

Leave Comments

neoevoke소셜계의 김성모

[usaco] 1.2 Milking Cows - usaco

Trackbacks 0

Comments 0

Leave Comments

Category

Recent Post

Recent Comment

Recent Trackback

Tag