| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Greedy Algorithm accepted in 0ms.#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator