Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Greedy Algorithm accepted in 0ms.

Posted by 2007011268 at 2012-08-12 15:50:17 on Problem 1083
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 200;
struct Node
{
	int start, end;
} table[N];
int res[N];
int group_cnt;
int end[N];
struct less_end
{
	bool operator()(const int a, const int b)
	{
		return table[a].end < table[b].end;
	}
};
void get_res()
{
	int n, s, t;
	cin >> n;
	for(int i=0; i<n; i++)
	{
		cin >> s >> t;
		table[i].start = min(s, t);
		table[i].end = max(s, t);
		if(table[i].start % 2 == 0)
			table[i].start --;
		if(table[i].end % 2 == 1)
			table[i].end ++;
		res[i] = i;
	}
	sort(res, res+n, less_end());

	group_cnt = 0;
	memset(end, 0, sizeof(end));

	for(int i=0; i<n; i++)
	{
		int idx = -1;
		int max_end = 0;
		for(int j=0; j<group_cnt; j++)
		{
			if(end[j] < table[res[i]].start)
			{
				if(end[j] > max_end)
				{
					max_end = end[j];
					idx = j;
				}
			}
		}
		if(idx == -1)
		{
			end[group_cnt++] = table[res[i]].end;
		}
		else
		{
			end[idx] = table[res[i]].end;
		}
	}
	cout << group_cnt * 10 << endl;
}
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		get_res();
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator